Paper: Two-Variable Descriptions of Regularity (at LICS 1999)

Authors: Erich Grädel Eric Rosen

Abstract

We prove that the class of all languages that are definable in \math, that is, in (non-monadic) existential second-order logic with only two first-order variables, coincides with the regular languages. This provides an alternative logical description of regularity to both the traditional one in terms of monadic second-order logic, due to Bühi and Trakhtenbrot, and the more recent ones in terms of prefix fragments of existential second-orderlogic due to Eiter, Gottlob and Gurevich.Our result extends to more general settings than words. Indeed, definability in \mathcoincides with recognizability by appropriate notions of automata on a large class of objects, including infinite words, trees, pictures and, more generally, all weakly deterministic, triangle-free transition systems.

BibTeX

  @InProceedings{GrdelRosen-TwoVariableDescript,
    author = 	 {Erich Grädel and Eric Rosen},
    title = 	 {Two-Variable Descriptions of Regularity},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS 1999)},
    year =	 {1999},
    month =	 {July}, 
    pages =      {14--23},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }