Deciding LTL over Mazurkiewicz traces

✍ Scribed by Benedikt Bollig; Martin Leucker

• Book ID: 104308849
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 224 KB
• Volume: 44
• Category: Article
• ISSN: 0169-023X
• DOI: 10.1016/s0169-023x(02)00136-2

✦ Synopsis

Linear temporal logic (LTL) has become a well established tool for specifying the dynamic behaviour of reactive systems with an interleaving semantics, and the automata-theoretic approach has proven to be a very useful mechanism for performing automatic verification in this setting. Especially alternating automata turned out to be a powerful tool in constructing efficient yet simple to understand decision procedures and directly yield further on-the-fly model checking procedures. In this paper, we exhibit a decision procedure for LTL over Mazurkiewicz traces that generalises the classical automata-theoretic approach to a LTL interpreted no longer over sequences but certain partial orders. Specifically, we construct a (linear) alternating B€ u uchi automaton (ABA) accepting the set of linearisations of traces satisfying the formula at hand. The salient point of our technique is to apply a notion of independence-rewriting to formulas of the logic. Furthermore, we show that the class of linear and trace-consistent ABA corresponds exactly to LTL formulas over Mazurkiewicz traces, lifting a similar result from L€ o oding and Thomas formulated in the framework of LTL over words.