zbMATH — the first resource for mathematics

Antichains: Alternative algorithms for LTL satisfiability and model-checking. (English) Zbl 1134.68404
Ramakrishnan, C. R. (ed.) et al., Tools and algorithms for the construction and analysis of systems. 14th international conference, TACAS 2008, held as part of the joint European conferences on theory and practice of software, ETAPS 2008, Budapest, Hungary, March 29–April 6, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78799-0/pbk). Lecture Notes in Computer Science 4963, 63-77 (2008).
Summary: The linear temporal logic (LTL) was introduced by Pnueli as a logic to express properties over the computations of reactive systems. Since this seminal work, there have been a large number of papers that have studied deductive systems and algorithmic methods to reason about the correctness of reactive programs with regard to LTL properties. In this paper, we propose new efficient algorithms for LTL satisfiability and model-checking. Our algorithms do not construct nondeterministic automata from LTL formulas but work directly with alternating automata using efficient exploration techniques based on antichains.
For the entire collection see [Zbl 1133.68009].

68Q60 Specification and verification (program logics, model checking, etc.)
03B44 Temporal logic
Full Text: DOI