论文标题
一阶逻辑的普通语言带有一条交替
The Regular Languages of First-Order Logic with One Alternation
论文作者
论文摘要
具有一阶逻辑表达的中性字母的普通语言，具有一个交替的特征。具体而言，显示出，如果任意$σ_2$公式定义了带有中性字母的常规语言，则只有一个仅使用顺序谓词的等效$σ_2$公式。这表明，所谓的Straubing的中央猜想以$σ_2$的语言持有中性字母，这是20多年来猜想的第一个进展。为了显示表征，开发了针对多项式大小的深度-3布尔电路，并开发了恒定顶部扇形。组合论点的核心在于研究语言中的立场如何彼此确定，这是一种独立利益的技术。
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 $Σ_2$ formula defines a regular language with a neutral letter, then there is an equivalent $Σ_2$ formula that only uses the order predicate. This shows that the so-called Central Conjecture of Straubing holds for $Σ_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.
