Paper: LTL with the Freeze Quantifier and Register Automata (at LICS 2006)

Authors: Stéphane Demri Ranko Lazic

Abstract

Temporal logics, first-order logics, and automata over data words have recently attracted considerable attention. A data word is a word over a finite alphabet, together with a datum (an element of an infinite domain) at each position. Examples include timed words and XML documents. To refer to the data, temporal logics are extended with the freeze quantifier, first-order logics with predicates over the data domain, and automata with registers or pebbles. We investigate relative expressiveness and complexity of standard decision problems for LTL with the freeze quantifier (LTL«), 2-variable first-order logic (FO2) over data words, and register automata. The only predicate available on data is equality. Previously undiscovered connections among those formalisms, and to counter automata with incrementing errors, enable us to answer several questions left open in recent literature. We show that the future-time fragment of LTL« which corresponds to FO2 over finite data words can be extended considerably while preserving decidability, but at the expense of non-primitive recursive complexity, and that most of further extensions are undecidable. We also prove that surprisingly, over infinite data words, LTL« without the 'unti' operator, as well as nonemptiness of one-way universal register automata, are undecidable even when there is only 1 register.

BibTeX

  @InProceedings{DemriLazic-LTLwiththeFreezeQua,
    author = 	 {Stéphane Demri and Ranko Lazic},
    title = 	 {LTL with the Freeze Quantifier and Register Automata},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {17--26},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }