Decidability of uniform recurrence of morphic sequences

DOI10.1142/S0129054113500032zbMATH Open1286.68279OpenAlexW2963927623MaRDI QIDQ2841990FDOQ2841990

Authors Fabien Durand 

Publication date 30 July 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5393

zbMATH Keywords

substitutiondecidabilitymorphismuniform recurrenceHD0L sequence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

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.

Recommendations

• ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
• Decidability, arithmetic subsequences and eigenvalues of morphic subshifts
• Decidability and \(k\)-regular sequences
• Complexité de suites engendrées par des récurrences unipotentes
• Undecidability of restricted uniform recurrence equations
• Recognizability for sequences of morphisms
• scientific article; zbMATH DE number 2087233
• On the complexity function for sequences which are not uniformly recurrent
• On factor complexity of morphic sequences
• Publication:3197899

Cites Work

• A characterization of substitutive sequences using return words
• A characterization of the Morse minimal set up to topological conjugacy
• Almost periodic sequences.
• An extension of Lagrange's theorem to interval exchange transformations over quadratic fields
• Cobham's theorem for substitutions
• Decidability of periodicity for infinite words
• Descendants of primitive substitutions
• Matching rules and substitution tilings
• More on morphisms and almost-periodicity
• Morphisms and almost-periodicity
• ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
• On the factors of automatic words
• On the periodicity of morphisms on free monoids
• On the simplification of infinite morphic words
• On the subword equivalence problem for morphic words
• Quelles tuiles ! (Pavages apériodiques du plan et automates bidimensionnels)
• Substitution dynamical systems: characterization of linear repetitivity and applications
• Substitutional dynamical systems, Bratteli diagrams and dimension groups
• Syndeticity and independent substitutions
• The ω sequence problem for DOL systems is decidable
• Tilings, substitution systems and dynamical systems generated by them
• \(K\)-groups associated with substitution minimal systems

Cited In (13)

• On almost periodicity of morphic sequences
• Self-induced systems
• Effective \(S\)-adic symbolic dynamical systems
• Iterative algebras.
• Morphic words and equidistributed sequences
• Recognizability for sequences of morphisms
• Decidability, arithmetic subsequences and eigenvalues of morphic subshifts
• A simple approach to minimal substitution subshifts
• Bracket words: A generalisation of Sturmian words arising from generalised polynomials
• A note on the base-\(p\) expansions of putative counterexamples to the \(p\)-adic Littlewood conjecture
• ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
• On uniform recurrence of a direct product
• Decidable problems in substitution shifts

This page was built for publication: Decidability of uniform recurrence of morphic sequences

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