论文标题
一阶公式定义的普通语言无量词交替
Regular languages defined by first-order formulas without quantifier alternation
论文作者
论文摘要
我们提供了一个简单的新证明，即通过一阶句子定义的普通语言没有量词更改，可以通过此类句子来定义，其中仅出现常规原子公式。此事实的早期证据取决于电路复杂性或代数的论点。我们的证明更为基础，仅使用有关有限自动机的最基本事实。
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.
