Decidability of uniform recurrence of morphic sequences
From MaRDI portal
Publication:2841990
DOI10.1142/S0129054113500032zbMATH Open1286.68279arXiv1204.5393OpenAlexW2963927623MaRDI QIDQ2841990FDOQ2841990
Authors: Fabien Durand 
Publication date: 30 July 2013
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1204.5393
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
- On the simplification of infinite morphic words
- Syndeticity and independent substitutions
- Cobham's theorem for substitutions
- Almost periodic sequences.
- Substitutional dynamical systems, Bratteli diagrams and dimension groups
- Matching rules and substitution tilings
- An extension of Lagrange's theorem to interval exchange transformations over quadratic fields
- Tilings, substitution systems and dynamical systems generated by them
- On the periodicity of morphisms on free monoids
- Decidability of periodicity for infinite words
- Descendants of primitive substitutions
- On the factors of automatic words
- A characterization of the Morse minimal set up to topological conjugacy
- \(K\)-groups associated with substitution minimal systems
- Substitution dynamical systems: characterization of linear repetitivity and applications
- Quelles tuiles ! (Pavages apériodiques du plan et automates bidimensionnels)
- The ω sequence problem for DOL systems is decidable
- Morphisms and almost-periodicity
- On the subword equivalence problem for morphic words
- More on morphisms and almost-periodicity
- ON UNIFORMLY RECURRENT MORPHIC SEQUENCES
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)
