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

DOI10.1145/3149822zbMath1407.03054OpenAlexW2963384346MaRDI QIDQ4608719

Howard Straubing, Andreas Krebs

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

Jidentitiesquantifier alternation\(\mathrm{FO}_2\)pseudovarities

Mathematics Subject Classification ID

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

Related Items (4)

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Conelikes and ranker comparisons ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ Varieties

This page was built for publication: An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic