Algebraic characterization of the alternation hierarchy in FO^2[<] on finite words

DOI10.4230/LIPICS.CSL.2011.525MaRDI QIDQ2915709zbMATH OpenOpenAlexFDO

Authors Howard Straubing

Publication date 18 September 2012

Full work available at URL https://dblp.uni-trier.de/db/conf/csl/csl2011.html#Straubing11

zbMATH Keywords

automatafinite model theory

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45)

Recommendations

• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• The \(\mathrm{FO}^2\) alternation hierarchy is decidable
• An effective characterization of the alternation hierarchy in two-variable logic

Cited in

(9)

• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• On logical hierarchies within \(\mathrm{FO}^{2}\)-definable languages
• From algebra to logic: there and back again. The story of a hierarchy (invited paper)
• An effective characterization of the alternation hierarchy in two-variable logic
• On FO 2 Quantifier Alternation over Words
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
• Finite-degree predicates and two-variable first-order logic
• An algebraic characterisation of first-order logic with neighbour

This page was built for publication: Algebraic characterization of the alternation hierarchy in \(\mathrm{FO}^2[<]\) on finite words

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