Decidability, arithmetic subsequences and eigenvalues of morphic subshifts

2018/11/09 by Durand, Fabien, Goyheneche, Valérie
#Discrete Mathematics (cs.DM) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1811.03942

Abstract

We prove decidability results on the existence of constant subsequences of uniformly recurrent morphic sequences along arithmetic progressions. We use spectral properties of the subshifts they generate to give a first algorithm deciding whether, given p ∈ N, there exists such a constant subsequence along an arithmetic progression of common difference p. In the special case of uniformly recurrent automatic sequences we explicitely describe the sets of such p by means of automata.

Related

• Decidability of uniform recurrence of morphic sequences
• On uniform recurrence of HD0l systems
• Coboundaries and eigenvalues of morphic subshifts
• On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
• Characterizing morphic sequences