The Regular Languages of First-Order Logic with One Alternation

Abstract

The regular languages with a neutral letter expressible in first-order logic with one alternation are characterized. Specifically, it is shown that if an arbitrary ${\Sigma }_2$ formula defines a regular language with a neutral letter, then there is an equivalent ${\Sigma }_2$ formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for ${\Sigma }_2$ over languages with a neutral letter, the first progress on the Conjecture in more than 20 years. To show the characterization, lower bounds against polynomial-size depth-3 Boolean circuits with constant top fan-in are developed. The heart of the combinatorial argument resides in studying how positions within a language are determined from one another, a technique of independent interest.

11 pages + bibliography, submitted to LICS'22