论文标题
关于Büchi算术的表现力
On the Expressiveness of Büchi Arithmetic
论文作者
论文摘要
我们表明，Büchi算术的存在片段严格不如任何基础的Büchi算术表达不足，此外，确定其$σ_2$碎片已经表现出来。此外，我们表明，在Büchi算术的存在片段中，多项式生长的普通语言是可以定义的。
We show that the existential fragment of Büchi arithmetic is strictly less expressive than full Büchi arithmetic of any base, and moreover establish that its $Σ_2$-fragment is already expressively complete. Furthermore, we show that regular languages of polynomial growth are definable in the existential fragment of Büchi arithmetic.
