On FO 2 Quantifier Alternation over Words

DOI10.1007/978-3-642-03816-7_44MaRDI QIDQ3182951zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• The \(\mathrm{FO}^2\) alternation hierarchy is decidable
• On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

Cites work

• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (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 2087227 (Why is no real title available?)
• scientific article; zbMATH DE number 798167 (Why is no real title available?)
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• An n! lower bound on formula size
• Classifying regular events in symbolic logic
• Expressive power of existential first-order sentences of Büchi's sequential calculus
• Logic Meets Algebra: the Case of Regular Languages
• On the lattice of sub-pseudovarieties of DA.
• Polynomial closure and unambiguous product
• Profinite semigroups, Mal'cev products, and identities
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• The lattice of pseudovarieties of idempotent semigroups and a non-regular analogue
• The succinctness of first-order logic on linear orders

Cited in

(13)

• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
• Level Two of the Quantifier Alternation Hierarchy over Infinite Words
• Rankers over infinite words (extended abstract)
• On the lattice of sub-pseudovarieties of DA.
• scientific article; zbMATH DE number 1775408 (Why is no real title available?)
• The \(\mathrm{FO}^2\) alternation hierarchy is decidable
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• SOME OPERATORS THAT PRESERVE THE LOCALITY OF A PSEUDOVARIETY OF SEMIGROUPS
• On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
• Pseudovarieties of ordered completely regular semigroups
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words

This page was built for publication: On FO 2 Quantifier Alternation over Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3182951)