The FO^2 alternation hierarchy is decidable

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

Authors Manfred Kufleitner, Pascal Weil

Publication date 22 November 2012

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

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)

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

Cited in

(20)

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

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)