On FO 2 Quantifier Alternation over Words

DOI10.1007/978-3-642-03816-7_44zbMath1250.03065OpenAlexW3125214380MaRDI QIDQ3182951

Manfred Kufleitner, Pascal Weil

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_44

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Related Items

Pseudovarieties of ordered completely regular semigroups ⋮ SOME OPERATORS THAT PRESERVE THE LOCALITY OF A PSEUDOVARIETY OF SEMIGROUPS ⋮ On the lattice of sub-pseudovarieties of DA.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the lattice of sub-pseudovarieties of DA.
• Classifying regular events in symbolic logic
• The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue
• Polynomial closure and unambiguous product
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Profinite semigroups, Mal'cev products, and identities
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• An n  ! lower bound on formula size
• The succinctness of first-order logic on linear orders
• Logic Meets Algebra: the Case of Regular Languages