论文标题
线性计算系统的终极周期性问题
Ultimate periodicity problem for linear numeration systems
论文作者
论文摘要
我们解决以下决策问题。给定一个计数系统$ u $和$ u $ - 验证套件$ x \ subseteq \ mathbb {n} $，即其贪婪的$ u $ - 代表的集合可以通过有限的automaton识别，确定$ x $是否最终定期。我们证明，对于基于线性循环序列构建的大量计算系统，这是可决定的。基于对复发方程和$ p $ - adiC方法的算术考虑，作为输入的DFA提供了对可允许的测试期的界限。
We address the following decision problem. Given a numeration system $U$ and a $U$-recognizable set $X\subseteq\mathbb{N}$, i.e. the set of its greedy $U$-representations is recognized by a finite automaton, decide whether or not $X$ is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linearly recurrent sequences. Based on arithmetical considerations about the recurrence equation and on $p$-adic methods, the DFA given as input provides a bound on the admissible periods to test.
