Balances of m-bonacci Words

• Autorzy: Břinda K. , Pelantová E. , Turek O.

Identyfikatory

DOI

10.3233/FI-2014-1031

• Języki publikacji: EN

Abstrakty

EN

The m-bonacci word is a generalization of the Fibonacci word to the m-letter alphabet A = {0, . . . ,m − 1}. It is the unique fixed point of the Pisot–type substitution ϕm: 0 → 01, 1 → 02, . . . , (m − 2) → 0(m− 1), and (m − 1) → 0. A result of Adamczewski implies the existence of constants c^(m) such that the m-bonacci word is c^(m) -balanced, i.e., numbers of letter a occurring in two factors of the same length differ at most by c^(m) for any letter a ∈ A. The constants c^(m) have been already determined for m = 2 and m = 3. In this paper we study the bounds c^(m) for a general m ≥ 2. We show that the m-bonacci word is ([κm] + 12)-balanced, where κ ≈ 0.58. For m ≤ 12, we improve the constant c^(m) by a computer numerical calculation to the value [wzór ].

Słowa kluczowe

EN

Balance property; m-bonacci word

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 132, nr 1
• Strony: 33--61
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Břinda K.

• FNSPE Czech Technical University in Prague, Trojanova 13, 120 00 Praha 2, Czech Republic

autor

Pelantová E.

• FNSPE Czech Technical University in Prague, Trojanova 13, 120 00 Praha 2, Czech Republic

autor

Turek O.

• Laboratory of Physics, Kochi University of Technology, Tosa Yamada, Kochi 782-8502, Japan

Bibliografia

• [1] B. Adamczewski. Balances for fixed points of primitive substitutions. Theor. Comput. Sci. 307, pp. 47–75, 2003.
• [2] B. Adamczewski. Symbolic discrepancy and self-similar dynamics. Ann. de l’inst. Four. 54, pp. 2201–2234, 2004.
• [3] J. Berstel. Recent results on extensions of Sturmian words, International Conference on Geometric and Combinatorial Methods in Group Theory and Semigroup Theory (Lincoln, NE, 2000). Internat. J. Algebra Comput. 12, no. 1–2, pp. 371–385, 2002.
• [4] V. Berthé, J. Cassaigne, and W. Steiner. Balance properties of Arnoux–Rauzy words. arXiv:1212.5106, 2012.
• [5] A. Brauer. On algebraic equations with all but one root in the interior of the unit circle. Math. Nachr. 4, pp. 250–257, 1951.
• [6] J. Cassaigne, S. Ferenczi, and L. Q. Zamboni. Imbalances in Arnoux–Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50, no. 4, pp. 1265–1276, 2000.
• [7] J.-M. Dumont and A. Thomas. Systémes de numération et fonctions fractales relatifs aux substitutions. Theor. Comput. Sci. 65, pp. 153–169, 1989.
• [8] A. Glen and J. Justin. Episturmian words: a survey. RAIRO – Theor. Inf. Appl. 43, pp. 402–433, 2009.
• [9] M. Morse and G. A. Hedlund. Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62, pp. 1–42, 1940.
• [10] M. Queffélec. Substitution Dynamical Systems – Spectral Analysis. Lecture Notes in Mathematics 1294, 1987.
• [11] G. Rauzy. Sequences defined by iterated morphisms. Sequences (Naples/Positano, 1988), pp. 275–286. Springer, 1990.
• [12] G. Richomme, K. Saari, and L. Q. Zamboni. Balance and Abelian complexity of the Tribonacci word. Adv. in App. Math. 45, pp. 212–231, 2010.
• [13] O. Turek. Abelian complexity and Abelian co-decomposition. Theor. Comput. Sci. 469, pp. 77–91, 2013.
• [14] L. Vuillon. Balanced words. Bull. Belg. Math. Soc. Simon Stevin. 10, pp. 787–805, 2003.