Decidability and k-Regular Sequences

DOI10.1016/J.TCS.2022.01.018MaRDI QIDQ6341033arXivFDO

Authors Daniel Krenn, Jeffrey Shallit

Publication date 19 May 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.01.018

Mathematics Subject Classification ID

Automata sequences (11B85) Formal languages and automata (68Q45) Combinatorics on words (68R15)

arXiv classification

cs.CCcs.DMcs.FLmath.CO

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.

This page was built for publication: Decidability and k-Regular Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6341033)