One quantifier alternation in first-order logic with modular predicates
From MaRDI portal
Abstract: Adding modular predicates yields a generalization of first-order logic FO over words. The expressive power of FO[<,MOD] with order comparison and predicates for has been investigated by Barrington, Compton, Straubing and Therien. The study of FO[<,MOD]-fragments was initiated by Chaubard, Pin and Straubing. 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 Sigma2[<,MOD]. The fragment Sigma2 consists of first-order formulas in prenex normal form with two blocks of quantifiers starting with an existential block. In addition we show that Delta2[<,MOD], the largest subclass of Sigma2[<,MOD] which is closed under negation, has the same expressive power as two-variable logic FO2[<,MOD]. This generalizes the result FO2[<] = Delta2[<] of Therien and Wilke to modular predicates. As a byproduct, we obtain another decidable characterization of FO2[<,MOD].
Recommendations
- Two-variable first order logic with modular predicates over words
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- The \(\mathrm{FO}^2\) alternation hierarchy is decidable
- Alternation hierarchies of first order logic with regular predicates
- Quantifier alternation in two-variable first-order logic with successor is decidable
Cites work
- A generalization of the Schützenberger product of finite monoids
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Constrained Steiner trees in Halin graphs
- Finite semigroup varieties of the form V*D
- scientific article; zbMATH DE number 2086254 (Why is no real title available?)
- scientific article; zbMATH DE number 4028925 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- scientific article; zbMATH DE number 1944133 (Why is no real title available?)
- scientific article; zbMATH DE number 2016845 (Why is no real title available?)
- scientific article; zbMATH DE number 1775408 (Why is no real title available?)
- Lattices of logical fragments over words (extended abstract)
- On finite monoids having only trivial subgroups
- On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
- Polynomial closure and unambiguous product
- Polynomial operations and hierarchies of concatenation
- Regular languages defined by generalized first-order formulas with a bounded number of bound variables
- Regular languages defined with generalized quantifiers
- Regular languages in \(NC\)
- SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
- The Join Levels of the Trotter-Weil Hierarchy Are Decidable
- Two-variable first order logic with modular predicates over words
Cited in
(11)- Level two of the quantifier alternation hierarchy over infinite words
- Two-variable first order logic with modular predicates over words
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- On the expressive power of FO[+]
- Covering and separation for logical fragments with modular predicates
- Level Two of the Quantifier Alternation Hierarchy over Infinite Words
- scientific article; zbMATH DE number 4189694 (Why is no real title available?)
- All about unambiguous polynomial closure
- Closing star-free closure
- Dot-depth three, return of the j-class
- First-order logics: some characterizations and closure properties
This page was built for publication: One quantifier alternation in first-order logic with modular predicates
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5245724)
