论文标题
关于Büchi算术中的解释
On Interpretations in Büchi Arithmetics
论文作者
论文摘要
Büchi算术BA_N，n> = 2，是前伯堡算术的延伸，其一单位函数符号v_n（x）表示n分割x的n最大幂。 BA_N中的集合的确定性等效于其n- ARY扩展中的有限自动机的可识别性。我们证明Büchi算术BA_N和BA_M对于任何n，m均可进行双解释。此外，我们确定BA_N中某种结构的任何解释都是对某些一维解释的同构。但是，这种同构不可能是可以定义的。
Büchi arithmetics BA_n, n >= 2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. Definability of a set in BA_n is equivalent to its recognizability by a finite automaton receiving numbers in their n-ary expansion. We show that Büchi arithmetics BA_n and BA_m are bi-interpretable for any n,m. Furthermore, we establish that any interpretation of some structure in BA_n is isomorphic to some one-dimensional interpretation; however, this isomorphism must not be BA_n-definable.
