Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
From MaRDI portal
Publication:3608423
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)
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
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
- Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
- Block products and nesting negations in \(\mathrm{FO}^{2}\)
- 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)
