ON UNIFORMLY RECURRENT MORPHIC SEQUENCES

DOI10.1142/S0129054109006966zbMath1187.68368OpenAlexW2117461107MaRDI QIDQ3646174

François Nicolas, Yuri Pritykin

Publication date: 19 November 2009

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

Full work available at URL: https://doi.org/10.1142/s0129054109006966

zbMATH Keywords

polynomial-time algorithmautomatic sequencemorphic sequencesub-word complexityuniformly recurrent sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50)

Related Items (4)

On almost periodicity of morphic sequences ⋮ ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES ⋮ Periodicity of morphic words ⋮ DECIDABILITY OF UNIFORM RECURRENCE OF MORPHIC SEQUENCES

Cites Work

• Unnamed Item
• Unnamed Item
• Substitutions in dynamics, arithmetics and combinatorics
• Substitution dynamical systems - spectral analysis
• Complexity of sequences and dynamical systems
• Iteration of maps by an automaton
• Almost periodic sequences.
• More on morphisms and almost-periodicity
• The monadic theory of morphic infinite words and generalizations
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• Repetition of subwords in DOL languages
• THE D0L ω-EQUIVALENCE PROBLEM
• The ω sequence problem for DOL systems is decidable
• Automatic Sequences
• Decidability of periodicity for infinite words
• Uniform tag sequences
• Constructions of strictly ergodic systems
• Symbolic Dynamics

This page was built for publication: ON UNIFORMLY RECURRENT MORPHIC SEQUENCES