Decidability and k-Regular Sequences
Abstract
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.
Collections
Cite this version of the work
Daniel Krenn, Jeffrey Shallit
(2020).
Decidability and k-Regular Sequences. UWSpace.
http://hdl.handle.net/10012/17966
Other formats