×

Some improvements of the \(S\)-adic conjecture. (English) Zbl 1247.37012

A sequence \(w\) over a finite alphabet is called \(S\)-adic if there exist a letter \(a\), a finite set of morphisms \(S\), and a sequence \((\sigma_n)_{n\in\mathbb{N}}\) of morphisms in \(S\) such that \(w=\lim_{n\to\infty} \sigma_0\sigma_1\cdots\sigma_n(a^\infty)\), see, e.g., [N. Pytheas Fogg (ed.) et al., Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794. Berlin: Springer (2002; Zbl 1014.11015)].
The \(S\)-adic conjecture is the existence of a condition \(C\) such that a sequence has a block-complexity in \(O(k)\) if and only if it is an \(S\)-adic sequence satisfying \(C\). Examples of \(S\)-adic sequences for some \(S\) are automatic sequences and fixed points of primitive morphisms.
The author proves that if a sequence is aperiodic, uniformly recurrent, and with block complexity \(O(k)\), then it is \(S\)-adic, improving a result due to S. Ferenczi [Ergodic Theory Dyn. Syst. 16, No. 4, 663–682 (1996; Zbl 0858.68051)].

MSC:

37B10 Symbolic dynamics
68R15 Combinatorics on words
11B85 Automata sequences
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche, J.-P.; Shallit, J., Automatic Sequences: Theory, Applications, Generalizations (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1086.11015
[2] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2 n + 1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[3] Berthé, V., Autour du système de numération dʼOstrowski, Journées Montoises dʼInformatique Théorique. Journées Montoises dʼInformatique Théorique, Marne-la-Vallée, 2000. Journées Montoises dʼInformatique Théorique. Journées Montoises dʼInformatique Théorique, Marne-la-Vallée, 2000, Bull. Belg. Math. Soc. Simon Stevin, 8, 209-239 (2001) · Zbl 0994.68100
[4] Berthé, V.; Holton, C.; Zamboni, L. Q., Initial powers of Sturmian sequences, Acta Arith., 122, 315-347 (2006) · Zbl 1117.37005
[5] (Berthé, V.; Rigo, M., Combinatorics, Automata and Number Theory. Combinatorics, Automata and Number Theory, Encyclopedia Math. Appl., vol. 135 (2010), Cambridge University Press: Cambridge University Press Cambridge) · Zbl 1197.68006
[6] Cassaigne, J., Special factors of sequences with linear subword complexity, (Developments in Language Theory, II. Developments in Language Theory, II, Magdeburg, 1995 (1996), World Sci. Publ.: World Sci. Publ. River Edge, NJ), 25-34 · Zbl 1096.68690
[7] Cassaigne, J., Complexité et facteurs spéciaux, Journées Montoises. Journées Montoises, Mons, 1994. Journées Montoises. Journées Montoises, Mons, 1994, Bull. Belg. Math. Soc. Simon Stevin, 4, 67-88 (1997) · Zbl 0921.68065
[8] Cassaigne, J., \(S\)-adiques (2009), online, private communication
[9] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[10] Durand, F., Linearly recurrent subshifts have a finite number of non-periodic subshift factors, Ergodic Theory Dynam. Systems, 20, 1061-1078 (2000) · Zbl 0965.37013
[11] Durand, F., Corrigendum and addendum to: “Linearly recurrent subshifts have a finite number of non-periodic subshift factors”, Ergodic Theory Dynam. Systems, 23, 663-669 (2003)
[12] Durand, F.; Host, B.; Skau, C., Substitutional dynamical systems, Bratteli diagrams and dimension groups, Ergodic Theory Dynam. Systems, 19, 953-993 (1999) · Zbl 1044.46543
[13] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoret. Comput. Sci., 1, 59-75 (1975) · Zbl 0316.68043
[14] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., On the number of subwords of everywhere growing DT0L languages, Discrete Math., 15, 223-234 (1976) · Zbl 0332.68053
[15] Ferenczi, S., Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité \(2 n + 1\), Bull. Soc. Math. France, 123, 271-292 (1995) · Zbl 0855.28008
[16] Ferenczi, S., Rank and symbolic complexity, Ergodic Theory Dynam. Systems, 16, 663-682 (1996) · Zbl 0858.68051
[17] Fogg, N. P., Substitutions in dynamics, arithmetics and combinatorics, (Berthé, V.; Ferenczi, S.; Mauduit, C.; Siegel, A., Lecture Notes in Math., vol. 1794 (2002), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1014.11015
[18] Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia Math. Appl., vol. 90 (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1001.68093
[19] Morse, M.; Hedlund, G. A., Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[20] Pansiot, J.-J., Complexité des facteurs des mots infinis engendrés par morphismes itérés, (Automata, Languages and Programming. Automata, Languages and Programming, Antwerp, 1984. Automata, Languages and Programming. Automata, Languages and Programming, Antwerp, 1984, Lecture Notes in Comput. Sci., vol. 172 (1984), Springer: Springer Berlin), 380-389 · Zbl 0554.68053
[21] Richomme, G., Conjugacy and episturmian morphisms, Theoret. Comput. Sci., 302, 1-34 (2003) · Zbl 1044.68142
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.