Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/LICS.2006.24 | Seattle, WA |
Keywords | Field | DocType |
Boolean algebra,decidability,formal languages,group theory,algebraic characterization,decidability,existential formula Boolean combinations,existential formula expressive power,first order logic,modular predicates,ordered colored structures,regular language combinatorial description,semigroup theory,syntactic morphisms | Discrete mathematics,Combinatorics,Formal language,Algebra,Computer science,Decidability,Mathematical proof,First-order logic,Boolean algebra,Regular language,Semigroup,Morphism | Conference |
ISSN | ISBN | Citations |
1043-6871 | 0-7695-2631-4 | 12 |
PageRank | References | Authors |
0.56 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laura Chaubard | 1 | 97 | 5.96 |
| Jean-Eric Pin | 2 | 632 | 67.86 |
| Howard Straubing | 3 | 528 | 60.92 |