From algebra to logic: there and back again -- the story of a hierarchy

2014/06/03 by Pascal Weil, Weil, Pascal
Computer Science · #semigroups and automata theory #Logic, programming, and type systems #Algorithms and Data Compression

paper · doi:10.48550/arxiv.1406.1035

Abstract

This is an extended survey of the results concerning a hierarchy of languages that is tightly connected with the quantifier alternation hierarchy within the two-variable fragment of first order logic of the linear order.

Related

• An effective characterization of the alternation hierarchy in two-variable logic
• Going higher in the First-order Quantifier Alternation Hierarchy on Words
• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Structure Theorem and Strict Alternation Hierarchy for FO² on Words