An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic

DOI10.1145/3149822MaRDI QIDQ4608719zbMATH OpenOpenAlexWikidataFDO

Authors A. Krebs, Howard Straubing

Publication date 22 March 2018

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2012/3850/

zbMATH Keywords

\(\mathrm{FO}_2\)identitiesJpseudovaritiesquantifier 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
• Publication:4725752
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• Two-variable logic with two order relations (extended abstract)
• Alternating (in)dependence-friendly logic
• Alternation and the computational complexity of logic programs
• Mathematical Foundations of Computer Science 2005
• Two-Variable Logic over Countable Linear Orderings
• Foundations of Information and Knowledge Systems

Cited in

(10)

• Varieties
• 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)
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• An effective characterization of the alternation hierarchy in two-variable logic
• Bounds for the quantifier depth in finite-variable logics: alternation hierarchy
• scientific article; zbMATH DE number 7533353 (Why is no real title available?)
• Conelikes and ranker comparisons
• Forbidden Patterns for FO² Alternation Over Finite and Infinite Words
• Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words

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 Q4608719)