Finite-degree predicates and two-variable first-order logic
From MaRDI portal
Subsystems of classical logic (including intuitionistic logic) (03B20) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Abstract: We consider two-variable first-order logic on finite words with a fixed number of quantifier alternations. We show that all languages with a neutral letter definable using the order and finite-degree predicates are also definable with the order predicate only. From this result we derive the separation of the alternation hierarchy of two-variable logic on this signature.
Recommendations
- Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
- Alternation hierarchies of first order logic with regular predicates
- Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
- Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
- Quantifier alternation in two-variable first-order logic with successor is decidable
Cited in
(3)
This page was built for publication: Finite-degree predicates and two-variable first-order logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351986)
