Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

First Annual IEEE Symposium on

Logic in Computer Science (LICS 1986)

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={S1,..,Sp} 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}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski