Paper: First order formulas with modular predicates (at LICS 2006)

Authors: Laura Chaubard Jean-Eric Pin Howard Straubing

Abstract

Two results by Schutzenberger (1965) and by Mc- Naughton and Papert (1971) lead to a precise description of the expressive power of first order logic on words interpreted as ordered colored structures. In this paper, we study the expressive power of existential formulas and of Boolean combinations of existential formulas in a logic enriched by modular numerical predicates. We first give a combinatorial description of the corresponding regular languages, and then give an algebraic characterization in terms of their syntactic morphisms. It follows that one can effectively decide whether a given regular language is captured by one of these two fragments of first order logic. The proofs rely on nontrivial techniques of semigroup theory: stamps, derived categories and wreath products.

BibTeX

  @InProceedings{ChaubardPinStraubin-Firstorderformulasw,
    author = 	 {Laura Chaubard and Jean-Eric Pin and Howard Straubing},
    title = 	 {First order formulas with modular predicates},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {211--220},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }