We show that the existential fragment of B\"uchi arithmetic is strictly less expressive than full B\"uchi arithmetic of any base, and moreover establish that its $\Sigma_2$-fragment is already expressively complete. Furthermore, we show that regular languages of polynomial growth are definable in the existential fragment of B\"uchi arithmetic.
翻译：我们证明B\“uchi 算术”的存在部分严格来说比任何基数的完整 B\\\“uchi 算术”的表达性要弱,此外,我们证明其$\Sigma_2$的碎片已经明确完成。 此外,我们证明,常规的多元增长语言在B\\“uchi 算术”的存在部分中是可以定义的。
相关内容
相关VIP内容
相关资讯
相关论文
微信扫码咨询专知VIP会员