One quantifier alternation in first-order logic with modular predicates

DOI10.1051/ita/2014024zbMath1339.03014arXiv1310.5043OpenAlexW2964015538MaRDI QIDQ5245724

Manfred Kufleitner, Tobias Walter

Publication date: 15 April 2015

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1310.5043

zbMATH Keywords

first-order logicfinite monoidlogical fragmentmodular predicatesyntactic homomorphism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (3)

Level two of the quantifier alternation hierarchy over infinite words ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Polynomial operations and hierarchies of concatenation
• Regular languages in \(NC\)
• Polynomial closure and unambiguous product
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Regular languages defined with generalized quantifiers
• Finite semigroup varieties of the form V*D
• Actions, wreath products of \(\mathcal C\)-varieties and concatenation product.
• On logical hierarchies within FO^2-definable languages
• The Join Levels of the Trotter-Weil Hierarchy Are Decidable
• Two-variable first order logic with modular predicates over words
• Lattices of Logical Fragments over Words
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Constrained Steiner trees in Halin graphs
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• On finite monoids having only trivial subgroups

This page was built for publication: One quantifier alternation in first-order logic with modular predicates