Bounds for the quantifier depth in finite-variable logics: alternation hierarchy

DOI10.4230/LIPICS.CSL.2013.61MaRDI QIDQ2958513zbMATH OpenFDO

Authors Christoph Berkholz, A. Krebs, Oleg Verbitsky

Publication date 2 February 2017

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2013.61

zbMATH Keywords

alternation hierarchyfinite-variable logic

Mathematics Subject Classification ID

Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13)

Recommendations

• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• Quantifier alternation in two-variable first-order logic with successor is decidable

Cited in

(6)

• Degrees of logics with Henkin quantifiers in poor vocabularies
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• scientific article; zbMATH DE number 458994 (Why is no real title available?)
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• Succinctness of Order-Invariant Logics on Depth-Bounded Structures
• Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps

This page was built for publication: Bounds for the quantifier depth in finite-variable logics: alternation hierarchy

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