On uniformly recurrent morphic sequences

Francois Nicolas, Yuri Pritykin

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the ThueMorse sequence, which play an important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence. A sequence x is called uniformly recurrent if for each finite subword u of x there exists an integer l such that u occurs in every l-length subword of x. The paper mainly focuses on the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomial time on pure morphic sequences and on automatic sequences. In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence.

Original languageEnglish (US)
Pages (from-to)919-940
Number of pages22
JournalInternational Journal of Foundations of Computer Science
Volume20
Issue number5
DOIs
StatePublished - Oct 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)

Keywords

  • Automatic sequence
  • Morphic sequence
  • Polynomial-time algorithm
  • Sub-word complexity
  • Uniformly recurrent sequence

Fingerprint Dive into the research topics of 'On uniformly recurrent morphic sequences'. Together they form a unique fingerprint.

Cite this