Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Branching-Time Temporal Logic Extended with Qualitative Presburger Constraints
verfasst von : Laura Bozzelli, Régis Gascon
Erschienen in: Logic for Programming, Artificial Intelligence, and Reasoning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Recently,
LTL
extended with atomic formulas built over a constraint language interpreting variables in ℤ has been shown to have a decidable satisfiability and model-checking problem. This language allows to compare the variables at different states of the model and include periodicity constraints, comparison constraints, and a restricted form of quantification. On the other hand, the
CTL
counterpart of this logic (and hence also its
CTL*
counterpart which subsumes both
LTL
and
CTL
) has an undecidable model-checking problem. In this paper, we substantially extend the decidability border, by considering a meaningful fragment of
CTL*
extended with such constraints (which subsumes both the universal and existential fragments, as well as the
EF
-like fragment) and show that satisfiability and model-checking over relational automata that are abstraction of counter machines are decidable. The correctness and the termination of our algorithm rely on a suitable well quasi-ordering defined over the set of variable valuations.