An effective characterization of the alternation hierarchy in two-variable logic

DOI10.4230/LIPICS.FSTTCS.2012.86MaRDI QIDQ2957483zbMATH OpenFDO

Authors A. Krebs, Howard Straubing

Publication date 26 January 2017

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

zbMATH Keywords

\(\mathrm{FO}_2\)identitiespseudovaritiesquantifier alternation

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Decidability of theories and sets of sentences (03B25) Basic properties of first-order languages and structures (03C07) Automata and formal grammars in connection with logical questions (03D05)

Recommendations

• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• 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
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• The \(\mathrm{FO}^2\) alternation hierarchy is decidable

Cited in

(9)

• Varieties
• A topological approach to non-uniform complexity
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words
• From algebra to logic: there and back again. The story of a hierarchy (invited paper)
• Alternation hierarchies of first order logic with regular predicates
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• scientific article; zbMATH DE number 7533353 (Why is no real title available?)
• The amazing mixed polynomial closure and its applications to two-variable first-order logic

This page was built for publication: An effective characterization of the alternation hierarchy in two-variable logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957483)