论文标题
可决定性和k期限序列
Decidability and k-Regular Sequences
论文作者
论文摘要
在本文中，我们考虑了许多涉及k期限序列的自然决策问题。具体而言，它们源于增长率的下限和上限；在特别的界限中， - 图像， - 规律性（通过确定性有限自动机的识别性）和 - 因子，例如这种序列的正方形和文明。我们表明决策问题是不确定的。
In this paper we consider a number of natural decision problems involving k-regular sequences. Specifically, they arise from - lower and upper bounds on growth rate; in particular boundedness, - images, - regularity (recognizability by a deterministic finite automaton) of preimages, and - factors, such as squares and palindromes of such sequences. We show that the decision problems are undecidable.
