Paper: Two-Variable Descriptions of Regularity (at LICS 1999)
Authors: Erich Gradel Eric RosenAbstract
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{GradelRosen-TwoVariableDescript, author = {Erich Gradel and Eric Rosen}, title = {Two-Variable Descriptions of Regularity}, booktitle = {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999}, year = 1999, editor = {Giuseppe Longo}, month = {July}, pages = {14--23}, location = {Trento, Italy}, publisher = {IEEE Computer Society Press} }