Paper: Automata on the Integers, Recurrence Distinguishability, and the Equivalence and Decidability of Monadic Theories (at LICS 1986)

Authors: Dominique Perrin Paul E. Schupp

Abstract

In this article we study finite automata on the integers or, equivalently, the "homogeneous" monadic theory Mτ(Z,S) of integers together with the successor fuction and a finite family S={S₁,..,S_p} of distinguished subsets of Z but without a constant for 0. Thus individual elements are not definable and everything is invariant under shift. The monadic theories Mτ(Z,S) are closely related with problems in ergodic theory and symbolic dynamics.

BibTeX

  @InProceedings{PerrinSchupp-AutomataontheIntege,
    author = 	 {Dominique Perrin and Paul E. Schupp},
    title = 	 {Automata on the Integers, Recurrence Distinguishability, and the Equivalence and Decidability of Monadic Theories},
    booktitle =  {Proceedings of the First Annual IEEE Symposium on Logic in Computer Science (LICS 1986)},
    year =	 {1986},
    month =	 {June}, 
    pages =      {301--304 },
    location =   {Cambridge, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }