Decidability and k-regular sequences

In this paper we consider a number of natural decision problems involving k-regular sequences. Specifically, they arise from considering • 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 these decision problems are undecidable.

Authors

• Daniel Krenn
• Jeffrey Shallit

Keywords

• k-regular sequence
• Decidability
• Unsolvability