Decidability and k-Regular Sequences
arXiv:2005.09507 · doi:10.1016/j.tcs.2022.01.018
Abstract
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.