Name
Abstract | ||
|---|---|---|
Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[<, MOD] with order comparison x < y and predicates for x = i mod n has been investigated by Barrington et al. The study of FO[<, MOD]-fragments was initiated by Chaubard et al. More recently, Dartois and Paperman showed that definability in the two-variable fragment FO2[<, MOD] is decidable. In this paper we continue this line of work. We give an effective algebraic characterization of the word languages in Sigma(2)[<, MOD]. The fragment Sigma(2) consists of first-order formulas in prenex normal form with two blocks of quantifiers starting with an existential block. In addition we show that Delta(2)[<, MOD], the largest subclass of Sigma(2)[<, MOD] which is closed under negation, has the same expressive power as two-variable logic FO2[<, MOD]. This generalizes the result FO2[<] = Delta(2)[<] of Therien and Wilke to modular predicates. As a byproduct, we obtain another decidable characterization of FO2[<, MOD]. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1051/ita/2014024 | RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS |
Keywords | DocType | Volume |
Finite monoid,syntactic homomorphism,logical fragment,first-order logic,modular predicate | Journal | 49 |
Issue | ISSN | Citations |
1 | 0988-3754 | 2 |
PageRank | References | Authors |
0.39 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manfred Kufleitner | 1 | 171 | 21.00 |
| Tobias Walter | 2 | 117 | 10.92 |