|
Published Articles >> Table of Contents >> Abstract
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
pp. 211-220
First Order Formulas with Modular Ppredicates
Laura Chaubard, Universit´e Paris VII, France
Jean-Eric Pin, Universit´e Paris VII, France
Howard Straubing, Boston College, USA
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.24
Send link to a friend
| 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.
|
 Additional Information
|
Citation:
Laura Chaubard, Jean-Eric Pin, Howard Straubing,
"First Order Formulas with Modular Ppredicates,"
lics,
pp. 211-220,
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06),
2006
|
|
