Ostrowski Numeration Systems, Addition, and Finite Automata
Ostrowski Numeration Systems, Addition, and Finite Automata
复制标题
奥斯特洛夫斯基计数系统、加法和有限自动机
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. Terry
中科院分区：
文献类型：
--
作者：
Philipp Hieronymi;A. Terry
提出了一种计算Ostrowski计数系统中加法运算的初等三遍算法。当$a$是二次时，基于$a$的Ostrowski计数系统中的加法是有限自动机可识别的。我们推导出$Xsubseteq mathbb{N}^n$的子集可定义在$(mathbb{N}，+，V_a)$中，其中$V_a$是将自然数$x$映射到收敛的$a$的最小分母的函数，该函数出现在具有非零系数的$a$的Ostrowski表示中，当且仅当元素的Ostrowski表示集可被有限自动机识别。接着证明了$(mathbb{N}，+，Va)$理论的可判定性。
We present an elementary three pass algorithm for computing addition in Ostrowski numeration systems. When $a$ is quadratic, addition in the Ostrowski numeration system based on $a$ is recognizable by a finite automaton. We deduce that a subset of $Xsubseteq mathbb{N}^n$ is definable in $(mathbb{N},+,V_a)$, where $V_a$ is the function that maps a natural number $x$ to the smallest denominator of a convergent of $a$ that appears in the Ostrowski representation based on $a$ of $x$ with a non-zero coefficient, if and only if the set of Ostrowski representations of elements of $X$ is recognizable by a finite automaton. The decidability of the theory of $(mathbb{N},+,V_a)$ follows.