Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
DOI10.1007/978-3-540-74915-8_27zbMATH Open1168.03328OpenAlexW1569275717MaRDI QIDQ3608423FDOQ3608423
Authors: Philipp Weis, Neil Immerman 
Publication date: 5 March 2009
Published in: Computer Science Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-74915-8_27
Recommendations
- Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
- Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
- On FO 2 Quantifier Alternation over Words
- The \(\mathrm{FO}^2\) alternation hierarchy is decidable
- Quantifier alternation in two-variable first-order logic with successor is decidable
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Temporal logic (03B44) Basic properties of first-order languages and structures (03C07) Descriptive complexity and finite models (68Q19)
Cited In (10)
- Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
- Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
- Finite-degree predicates and two-variable first-order logic
- On the strictness of the quantifier structure hierarchy in first-order logic
- Block products and nesting negations in \(\mathrm{FO}^{2}\)
- Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
- On Simon's congruence closure of a string
- On FO 2 Quantifier Alternation over Words
- Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
- Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
This page was built for publication: Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608423)
