×
Adamczewski, Boris

Balances for fixed points of primitive substitutions. (English) Zbl 1059.68083

Theor. Comput. Sci. 307, No. 1, 47-75 (2003).
Summary: An infinite word defined over a finite alphabet \(\mathcal A\) is balanced if for any pair \((\omega,\omega')\) of factors of the same length and for any letter \(a\) in the alphabet \[ \| \omega |_a - | \omega' |_a | \leqslant 1, \] where \(| \omega |_a\) denotes the number of occurrences of the letter \(a\) in the word \(\omega\). In this paper, we generalize this notion and introduce a measure of balance for an infinite sequence. In the case of fixed points of primitive substitutions, we show that the asymptotic behaviour of this measure is in part ruled by the spectrum of the incidence matrix associated with the substitution. Connections with frequencies of letters and other balance properties are also discussed.

Cited in 34 Documents

MSC:

68R15 Combinatorics on words

Keywords:

Combinatorics on words; Balance; Primitive substitution; Frequency; Infinite words
PDFBibTeX XMLCite
\textit{B. Adamczewski}, Theor. Comput. Sci. 307, No. 1, 47--75 (2003; Zbl 1059.68083)
Full Text: DOI

References:

[1] B. Adamczewski, Symbolic discrepancy and self-similar dynamics, preprint, 2002.; B. Adamczewski, Symbolic discrepancy and self-similar dynamics, preprint, 2002. · Zbl 1066.11032
[2] Adamczewski, B., Codages de rotations et pénomènes d’autosimilarités, J. Théor. Nombres Bordeaux, 14, 351-386 (2002) · Zbl 1113.37003
[3] B. Adamczewski, Répartitions des suites \((nα)n∈N\); B. Adamczewski, Répartitions des suites \((nα)n∈N\) · Zbl 1060.11043
[4] Alessandri, P.; Berthé, V., Three distance theorems and combinatorics on words, Enseign. Math., 44, 2, 103-132 (1998) · Zbl 0997.11051
[5] Altman, E.; Gaujal, B.; Hordijk, A., Balanced sequences and optimal routing, J. ACM, 47, 752-775 (2000) · Zbl 1327.68180
[6] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. Soc. Math. France, 119, 199-215 (1991) · Zbl 0789.28011
[7] Berthé, V.; Tijdeman, R., Balance properties of multi-dimensional words, Theoret. Comput. Sci., 273, 197-224 (2002) · Zbl 0997.68091
[8] Canterini, V.; Siegel, A., Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc., 353, 5121-5144 (2001), (electronic) · Zbl 1142.37302
[9] Cassaigne, J.; Ferenczi, S.; Zamboni, L. Q., Imbalances in Arnoux-Rauzy sequences, Ann. Inst. Fourier (Grenoble), 50, 1265-1276 (2000) · Zbl 1004.37008
[10] Chacon, R. V., Weakly mixing transformations which are not strongly mixing, Proc. Amer. Math. Soc., 22, 559-562 (1969) · Zbl 0186.37203
[11] Coquet, J., A summation formula related to the binary digits, Invent. Math., 73, 107-115 (1983) · Zbl 0528.10006
[12] Coven, E. M.; Hedlund, G. A., Sequences with minimal block growth, Math. Systems Theory, 7, 138-153 (1973) · Zbl 0256.54028
[13] Crisp, D.; Moran, W.; Pollington, A.; Shiue, P., Substitution invariant cutting sequences, J. Théor. Nombres Bordeaux, 5, 123-137 (1993) · Zbl 0786.11041
[14] F.M. Dekking, On the distribution of digits in arithmetic sequences, in: Seminar on Number Theory, 1982-1983 (Talence, 1982/1983), pages Exp. No. 32, 12. Univ. Bordeaux I, Talence, 1983.; F.M. Dekking, On the distribution of digits in arithmetic sequences, in: Seminar on Number Theory, 1982-1983 (Talence, 1982/1983), pages Exp. No. 32, 12. Univ. Bordeaux I, Talence, 1983. · Zbl 0529.10047
[15] Didier, G., Codages de rotations et fractions continues, J. Number Theory, 71, 275-306 (1998) · Zbl 0921.11015
[16] Drmota, M.; Tichy, R. F., Sequences, Discrepancies and Applications (1997), Springer: Springer Berlin · Zbl 0877.11043
[17] Dumont, J.-M.; Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci., 65, 153-169 (1989) · Zbl 0679.10010
[18] Durand, F., A characterization of substitutive sequences using return words, Discrete Math., 179, 89-101 (1998) · Zbl 0895.68087
[19] 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
[20] 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
[21] Fagnot, I.; Vuillon, L., Generalized balances in Sturmian words, Discrete Appl. Math., 121, 83-111 (2002) · Zbl 1002.68117
[22] B. Gaujal, Convexité discrète et régularité; application au contrôle des systèmes à évènements discrets, Habilitation à diriger des recherches, LORIA et INRIA, 2001.; B. Gaujal, Convexité discrète et régularité; application au contrôle des systèmes à évènements discrets, Habilitation à diriger des recherches, LORIA et INRIA, 2001.
[23] Graham, R. L., Covering the positive integers by disjoint sets of the form {\([ nα +β]\): \(n=1,2\),…}, J. Combin. Theory Ser. A, 15, 354-358 (1973) · Zbl 0279.10042
[24] Holton, C.; Zamboni, L. Q., Geometric realizations of substitutions, Bull. Soc. Math. France, 126, 149-179 (1998) · Zbl 0931.11004
[25] Hubert, P., Suites équilibrées, Theoret. Comput. Sci., 242, 91-108 (2000) · Zbl 0944.68149
[26] L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience Wiley, New York, 1974, Pure Appl. Math.; L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences, Wiley-Interscience Wiley, New York, 1974, Pure Appl. Math. · Zbl 0281.10001
[27] Morikawa, R., On eventually covering families generated by the bracket function, Bull. Fac. Liberal Arts Nagasaki Univ., 23, 17-22 (1982/83) · Zbl 0506.10042
[28] Morse, M.; Hedlund, G. A., Symbolic dynamics, Amer. J. Math., 60, 815-866 (1938) · JFM 64.0798.04
[29] Morse, M.; Hedlund, G. A., Symbolic dynamics II. Sturmian trajectories, Amer. J. Math., 62, 1-42 (1940) · JFM 66.0188.03
[30] J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, in: Automata, Languages and Programming (Antwerp, 1984), Springer, Berlin, 1984, pp. 380-389.; J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés, in: Automata, Languages and Programming (Antwerp, 1984), Springer, Berlin, 1984, pp. 380-389. · Zbl 0554.68053
[31] Queffélec, M., Substitution Dynamical Systems—Spectral Analysis, Lecture Notes in Mathematics, Vol. 1294 (1987), Springer: Springer Berlin · Zbl 0642.28013
[32] Rauzy, G., Nombres algébriques et substitutions, Bull. Soc. Math. France, 110, 147-178 (1982) · Zbl 0522.10032
[33] G. Rauzy, Des mots en arithmétique, in: Avignon Conference on Language Theory and Algorithmic Complexity (Avignon, 1983), Univ. Claude-Bernard, Lyon, 1984, pp. 103-113.; G. Rauzy, Des mots en arithmétique, in: Avignon Conference on Language Theory and Algorithmic Complexity (Avignon, 1983), Univ. Claude-Bernard, Lyon, 1984, pp. 103-113. · Zbl 0553.10041
[34] G. Rauzy, Sequences defined by iterated morphisms, in: Sequences (Naples/Positano, 1988), Springer, New York, 1990, pp. 275-286.; G. Rauzy, Sequences defined by iterated morphisms, in: Sequences (Naples/Positano, 1988), Springer, New York, 1990, pp. 275-286. · Zbl 0955.28501
[35] Rote, G., Sequences with subword complexity \(2n\), J. Number Theory, 46, 196-213 (1994) · Zbl 0804.11023
[36] Rudin, W., Some theorems on Fourier coefficients, Proc. Amer. Math. Soc., 10, 855-859 (1959) · Zbl 0091.05706
[37] H. Shapiro, Extremal problems for polynomials and power series, Ph.D. Thesis, Massachusetts Institute of Technology, 1951.; H. Shapiro, Extremal problems for polynomials and power series, Ph.D. Thesis, Massachusetts Institute of Technology, 1951.
[38] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, in: Algebraic Number Theory and Diophantine Analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 467-483.; R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, in: Algebraic Number Theory and Diophantine Analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 467-483. · Zbl 0971.11003
[39] Tijdeman, R., Fraenkel’s conjecture for six sequences, Discrete Math., 222, 223-234 (2000) · Zbl 1101.11314
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.