LTL with the Freeze Quantifier and Register Automata

Stéphane Demri (1, 2, 3) , Ranko Lazić (4)

1 LSV - Laboratoire Spécification et Vérification
2 CNRS - Centre National de la Recherche Scientifique
3 DAHU - Verification in databases
4 University of Warwick [Coventry]

A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. To reason about data words, linear temporal logic is extended by the freeze quantifier, which stores the element at the current word position into a register, for equality comparisons deeper in the formula. By translations from the logic to alternating automata with registers and then to faulty counter automata whose counters may erroneously increase at any time, and from faulty and error-free counter automata to the logic, we obtain a complete complexity table for logical fragments defined by varying the set of temporal operators and the number of registers. In particular, the logic with future-time operators and 1 register is decidable but not primitive recursive over finite data words. Adding past-time operators or 1 more register, or switching to infinite data words, cause undecidability.

Mots clés: data word; alternating register automaton; freeze quantifier; linear-time temporal logic; counter machine; incrementing error; complexity; undecidability

Domaines: Informatique [cs]; Logique en informatique [cs.LO]; Théorie et langage formel [cs.FL]

Stéphane Demri, Ranko Lazić. LTL with the Freeze Quantifier and Register Automata. ACM Transactions on Computational Logic, 2009, 10 (3), ⟨10.1145/1507244.1507246⟩. ⟨hal-03189491⟩