Logic in Computer Science (LICS 2003)

Paper: Spectra of Monadic Second-Order Formulas with One Unary Function (at LICS 2003)

Authors: Yuri Gurevich Saharon Shelah

Abstract

We establish the eventual periodicity of the spectrum of any monadic second-order formula where (i) all relation symbols, except equality, are unary, and (ii) there is only one function symbol and that symbol is unary.

BibTeX

  @InProceedings{GurevichShelah-SpectraofMonadicSec,
    author = 	 {Yuri Gurevich and Saharon Shelah},
    title = 	 {Spectra of Monadic Second-Order Formulas with One Unary Function},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {291--300},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }