Well-balanced sequences. (Suites équilibrées.) (French) Zbl 0944.68149

Hubert, P.

Theor. Comput. Sci. 242, No. 1-2, 91-108 (2000).

Summary: Well-balanced sequences are one of the possible generalizations of sturmian sequences. We give a combinatoric and geometric interpretation of non-periodic well-balanced sequences. We compute the complexity of these sequences for integers large enough.

MSC:

68R15	Combinatorics on words
11B85	Automata sequences

Keywords:

non-periodic well-balanced sequences; generalizations of Sturmian sequences; complexity

References:

[1]	P. Alessandri, V. Berthé, Three distances theorems and combinatorics on words, preprint.; P. Alessandri, V. Berthé, Three distances theorems and combinatorics on words, preprint. · Zbl 0997.11051
[2]	Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. SMF, 119, 101-117 (1991) · Zbl 0789.28011
[3]	Berstel, J.; Pocciola, M., A geometric proof of the enumeration formula for Sturmian words, Inform. J. Algebra Comput., 3, 349-355 (1993) · Zbl 0802.68099
[4]	Corfeld, I. P.; Formin, S. V.; G. Sinai, Ya., Ergodic Theory (1982), Springer: Springer Berlin · Zbl 0493.28007
[5]	Coven, E. M.; Hedlund, G. A., Sequences with minimal block growth, Math. Systems Theory, 7, 2 (1973) · Zbl 0256.54028
[6]	Duluc, S.; Gouyou-Beauchamps, D., Sur les facteurs des suites de sturm, Theoret. Comput. Sci., 71, 381-400 (1990) · Zbl 0694.68048
[7]	Fezenczi, S., Bounded remainder sets, Acta Arithmetica LXI., 4, 319-326 (1992) · Zbl 0774.11037
[8]	Hedlund, G. A.; Morse, M., Symbolic dynamics II. sturmian trajectories, Amer. J. Math., 62 (1940) · JFM 66.0188.03
[9]	L. Graham, R., Covering the Positive Integers by disjoints sets of the form \({[n α + β] :n=1,2,… }\), J. Combin. Theory Ser, A15, 354-358 (1973) · Zbl 0279.10042
[10]	de Luca, A.; Mignosi, F., Some combinatorial properties of Sturmian words, Theoret. Comput. Sci., 136, 361-385 (1994) · Zbl 0874.68245
[11]	Mignosi, F., On the number of factors of Sturmian words, Theoret. Comput. Sci., 82, 71-84 (1991) · Zbl 0728.68093
[12]	G. Rauzy, Ensembles à restes bornés, Séminaire de théorie des nombres de Bordeaux, Exposé 24, 1983-1984.; G. Rauzy, Ensembles à restes bornés, Séminaire de théorie des nombres de Bordeaux, Exposé 24, 1983-1984. · Zbl 0547.10044
[13]	G. Rauzy, Mots infinis en arithmétique, Automata on Infinite Words, Lecture Notes in Computer Science, vol. 192, Springer, Berlin, 1985, pp. 165-171.; G. Rauzy, Mots infinis en arithmétique, Automata on Infinite Words, Lecture Notes in Computer Science, vol. 192, Springer, Berlin, 1985, pp. 165-171. · Zbl 0613.10044
[14]	Séébold, P., Fibonacci morphisms and sturmian words, Theoret. Comput. Sci., 88, 367-384 (1991) · Zbl 0737.68068