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

2012/05/22 by Krebs, Andreas, Straubing, Howard
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1205.4802

Abstract

We characterize the languages in the individual levels of the quantifier alternation hierarchy of first-order logic with two variables by identities. This implies decidability of the individual levels. More generally we show that the two-sided semidirect product of a decidable variety with the variety J is decidable.

Related

• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
• Going higher in the First-order Quantifier Alternation Hierarchy on Words
• From algebra to logic: there and back again -- the story of a hierarchy
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• The Alternation Hierarchy of First-Order Logic on Words is Decidable