The FO^2 alternation hierarchy is decidable

DOI10.4230/LIPICS.CSL.2012.426zbMATH Open1252.03021arXiv1203.6152MaRDI QIDQ4649563FDOQ4649563

Authors: Manfred Kufleitner, Pascal Weil 

Publication date: 22 November 2012

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

Recommendations

• On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
• On FO 2 Quantifier Alternation over Words
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Quantifier alternation in two-variable first-order logic with successor is decidable
• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words

zbMATH Keywords

regular languagesemigroupautomata theoryfirst-order logiccondensed ranker

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Cited In (20)

• One quantifier alternation in first-order logic with modular predicates
• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
• The word problem for omega-terms over the Trotter-Weil hierarchy
• Forbidden Patterns for FO² Alternation Over Finite and Infinite Words
• The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Alternation hierarchies of first order logic with regular predicates
• On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
• Block products and nesting negations in \(\mathrm{FO}^{2}\)
• The amazing mixed polynomial closure and its applications to two-variable first-order logic
• An effective characterization of the alternation hierarchy in two-variable logic
• Quantifier alternation in two-variable first-order logic with successor is decidable
• On FO 2 Quantifier Alternation over Words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• Conelikes and ranker comparisons
• How many times do you need to go back to the future in unary temporal logic?
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
• From algebra to logic: there and back again. The story of a hierarchy (invited paper)

This page was built for publication: The \(\mathrm{FO}^2\) alternation hierarchy is decidable

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