Decidability of uniform recurrence of morphic sequences

2012/04/24 by Fabien Durand, Durand, Fabien
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1204.5393

arxiv created 2012/08/31 · arxiv updated 2012/09/03

Abstract

We prove that the uniform recurrence of morphic sequences is decidable. For this we show that the number of derived sequences of uniformly recurrent morphic sequences is bounded. As a corollary we obtain that uniformly recurrent morphic sequences are primitive substitutive sequences.

Related

• On uniform recurrence of HD0l systems
• On uniform recurrence of morphic sequences
• Decidability, arithmetic subsequences and eigenvalues of morphic subshifts
• On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
• A Taxonomy of Morphic Sequences