Decidability of uniform recurrence of morphic sequences

Preprint English OPEN
Durand , Fabien;
(2012)
  • Publisher: HAL CCSD
  • Subject: [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO] | Morphic sequences | Mathematics - Combinatorics | decidability | substitution | Computer Science - Discrete Mathematics | [ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM] | return words | derived sequences
    arxiv: Mathematics::K-Theory and Homology | Computer Science::Discrete Mathematics | Computer Science::Formal Languages and Automata Theory

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 substitut... View more
  • References (40)
    40 references, page 1 of 4

    [Boshernitzan and Carroll 1997] M. D. Boshernitzan and C. R. Carroll. An extension of Lagrange's theorem to interval exchange transformations over quadratic fields. J. Anal. Math. 72 (1997), 21-44.

    [Bratteli, Jorgensen, Kim and Roush 2001] O. Bratteli, P. Jorgensen, K. H. Kim, and F. Roush. Decidability of the isomorphism problem for stationary AF-algebras and the associated ordered simple dimension groups. Ergodic Theory Dynam. Systems 21 (2001), 1625-1655.

    [Bruy`ere, Hansel, Michaux, and Villemaire 1994] V. Bruy`ere, G. Hansel, C. Michaux, and R. Villemaire. Logic and p-recognizable sets of integers. Bull. Belg. Math. Soc. 1 (1994), 191-238. Corrigendum, Bull. Belg. Math. Soc. 1 (1994), 577.

    [Cˇ erny´ and Gruska 1986] A. Cˇ erny´ and J. Gruska. Modular trellises. In G. Rozenberg and A. Salomaa, editors, The Book of L, pp. 45-61. Springer-Verlag, 1986.

    [Coven, Keane and LeMasurier 2008] E. Coven, M. Keane, and M. LeMasurier. A characterization of the morse minimal set up to topological conjugacy. Ergodic Theory and Dynamical Systems 28 (2008), 1443-1451.

    [Culik and Harju 1984] K. Culik and T. Harju. The ω-sequence equivalence problem for D0L systems is decidable. J. Assoc. Comput. Mach. 31 (1984), 282-298.

    [Damanik and Lenz 2006] D. Damanik and D. Lenz. Substitution dynamical systems: Characterization of linear repetitivity and applications. J. Math. Anal. Appl. 321 (2006), 766-780.

    [Durand 1996] F. Durand. Contributions `a l'´etude des suites et syst`emes dynamiques substitutifs. PhD thesis, Universit´e de la M´editerran´ee, 1996.

    [Durand 1998] F. Durand. A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89-101.

    [Durand 2011] F. Durand. Cobham's theorem for substitutions. J. Eur. Math. Soc. 13 (2011), 1797-1812.

  • Metrics
Share - Bookmark