Incompleteness of States wrt Traces in Model Checking
<|reference_start|>Incompleteness of States wrt Traces in Model Checking: Cousot and Cousot introduced and studied a general past/future-time specification language, called mu*-calculus, featuring a natural time-symmetric trace-based semantics. The standard state-based semantics of the mu*-calculus is an abstract interpretation of its trace-based semantics, which turns out to be incomplete (i.e., trace-incomplete), even for finite systems. As a consequence, standard state-based model checking of the mu*-calculus is incomplete w.r.t. trace-based model checking. This paper shows that any refinement or abstraction of the domain of sets of states induces a corresponding semantics which is still trace-incomplete for any propositional fragment of the mu*-calculus. This derives from a number of results, one for each incomplete logical/temporal connective of the mu*-calculus, that characterize the structure of models, i.e. transition systems, whose corresponding state-based semantics of the mu*-calculus is trace-complete.<|reference_end|>
@article{giacobazzi2004incompleteness,
    title={Incompleteness of States w.r.t. Traces in Model Checking},
    author={Roberto Giacobazzi and Francesco Ranzato},
    journal={arXiv preprint arXiv:cs/0404048},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0404048},
    primaryClass={cs.LO}
}