Presburger liveness verification of discrete timed automata

✍ Scribed by Zhe Dang; Pierluigi San Pietro; Richard A. Kemmerer

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 259 KB
• Volume: 299
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00485-1

✦ Synopsis

Using an automata-theoretic approach, we investigate the decidability of liveness properties (called Presburger liveness properties) for timed automata when Presburger formulas on conÿgurations are allowed. While the general problem of checking a temporal logic such as TPTL augmented with Presburger clock constraints is undecidable, we show that there are various classes of Presburger liveness properties which are decidable for discrete timed automata. For instance, it is decidable, given a discrete timed automaton A and a Presburger property P, whether there exists an !-path of A where P holds inÿnitely often. We also show that other classes of Presburger liveness properties are indeed undecidable for discrete timed automata, e.g., whether P holds inÿnitely often for each !-path of A. These results might give insights into the corresponding problems for timed automata over dense domains, and help in the deÿnition of a fragment of linear temporal logic, augmented with Presburger conditions on conÿgurations, which is decidable for model checking timed automata.