The FO^2 alternation hierarchy is decidable
From MaRDI portal
Publication:4649563
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
Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)
Cited In (15)
- 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 FO2 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
- On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
- The amazing mixed polynomial closure and its applications to two-variable first-order logic
- On FO 2 Quantifier Alternation over Words
- Alternation Hierarchies of First Order Logic with Regular Predicates
- 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
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)
