Regular languages defined by first-order formulas without quantifier alternation

2022/08/22 by Krebs, Andreas, Straubing, Howard
#F.4.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2208.10480

Abstract

We give a simple new proof that regular languages defined by first-order sentences with no quantifier alteration can be defined by such sentences in which only regular atomic formulas appear. Earlier proofs of this fact relied on arguments from circuit complexity or algebra. Our proof is much more elementary, and uses only the most basic facts about finite automata.

Related

• The Regular Languages of First-Order Logic with One Alternation
• Lecture Notes on Monadic First- and Second-Order Logic on Strings
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• Generalizing input-driven languages: theoretical and practical benefits
• Going higher in the First-order Quantifier Alternation Hierarchy on Words