Study of irreducible balanced pairs for substitutive languages

Bernat, Julien

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 4, pp. 663-678.

Let $ℒ$ be a language. A balanced pair $(u,v)$ consists of two words $u$ and $v$ in $ℒ$ which have the same number of occurrences of each letter. It is irreducible if the pairs of strict prefixes of $u$ and $v$ of the same length do not form balanced pairs. In this article, we are interested in computing the set of irreducible balanced pairs on several cases of languages. We make connections with the balanced pairs algorithm and discrete geometrical constructions related to substitutive languages. We characterize substitutive languages which have infinitely many irreducible balanced pairs of a given form.

[1] B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003) 47-75. | MR | Zbl

[2] P. Ambrož, Z. Masáková, E. Pelantová and C. Frougny, Palindromic complexity of infinite words associated with simple Parry numbers. Ann. Inst. Fourier (Grenoble) 56 (2006) 2131-2160. | Numdam | MR | Zbl

[3] P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | MR | Zbl

[4] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité $2n+1$. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR | Zbl

[5] P. Arnoux, V. Berthé, H. Ei and S. Ito, Tilings, quasicrystals, discrete planes, generalized substitutions, and multidimensional continued fractions, in Discrete models: combinatorics, computation, and geometry (Paris, 2001). Discrete Math. Theor. Comput. Sci. Proc., AA, pp. 059-078 (electronic). Maison Inform. Math. Discrèt. (MIMD), Paris (2001). | MR | Zbl

[6] P. Arnoux, V. Berthé and S. Ito, Discrete planes, ${\mathbb{Z}}^2$-actions, Jacobi-Perron algorithm and substitutions. Ann. Inst. Fourier (Grenoble) 52 (2002) 305-349. | Numdam | MR | Zbl

[7] M. Barge and B. Diamond, Proximality in Pisot Tiling Spaces. Fund. Math. 194 (2007) 191-238. | MR | Zbl

[8] M. Barge and J. Kwapisz, Geometric theory of unimodular Pisot substitutions. Amer. J. Math. 128 (2006) 1219-1282. | MR | Zbl

[9] J. Bernat, Symmetrized $\beta$-integers (2006) Submitted. | Zbl

[10] J. Bernat, V. Berthé and H. Rao, On super-coincidence condition of substitutions (2006) Preprint.

[11] J. Berstel, Fibonacci words - a survey, in The Book of L, pp. 13-27. Springer-Verlag (1986). | Zbl

[12] V. Berthé and R. Tijdeman, Lattices and multi-dimensional words. Theoret. Comput. Sci. 319 (2004) 177-202. | MR | Zbl

[13] V. Canterini and A. Siegel, Geometric representation of substitutions of Pisot type. Trans. Amer. Math. Soc. 353 (2001) 5121-5144. | MR | Zbl

[14] J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000) 1265-1276. | Numdam | MR | Zbl

[15] A. De Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett. 12 (1981) 193-195. | MR | Zbl

[16] X. Droubay, Palindromes in the Fibonacci word. Inform. Process. Lett. 55 (1995) 217-221. | MR | Zbl

[17] X. Droubay, J. Justin and G. Pirillo, Epi-Sturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001) 539-553. | MR | Zbl

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

[19] F. Durand, B. Host and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergod. Theor. Dyn. Syst. 19 (1999) 953-993. | MR | Zbl

[20] S. Fabre, Dépendance de systèmes de numération associés à des puissances d'un nombre de Pisot. Theoret. Comput. Sci. 158 (1996) 65-79. | MR | Zbl

[21] C. Frougny, Confluent linear numeration systems. Theoret. Comput. Sci. 106 (1992) 183-219. | MR | Zbl

[22] B. Host, Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable. Ergod. Theor. Dyn. Syst. 6 (1986) 529-540. | MR | Zbl

[23] S. Ito and H. Rao, Atomic surfaces, tilings and coincidences I. Irreducible case. Israel J. Math. 153 (2006) 129-155. | MR | Zbl

[24] J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl. 36 (2002) 385-388. | Numdam | MR | Zbl

[25] A.N. Livshits, Some examples of adic transformations and automorphisms of substitutions. Selecta Math. Soviet. 11 (1992) 83-104. Selected translations. | MR | Zbl

[26] M. Lothaire, Algebraic Combinatorics On Words. Cambridge University Press (2002). | MR | Zbl

[27] B.F. Martensen, Generalized balanced pair algorithm. Topology Proc. 28 (2004) 163-178. | MR | Zbl

[28] W. Parry, On the $\beta$-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11 (1960) 401-416. | MR | Zbl

[29] N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatoric, edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Lecture Notes in Mathematics 1794 (2002). | MR | Zbl

[30] M. Queffélec, Substitution dynamical systems-spectral analysis. Lecture Notes in Mathematics 1294 (1987). | MR | Zbl

[31] R.N. Risley and L.Q. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95 (2000) 167-184. | MR | Zbl

[32] A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8 (1957) 477-493. | MR | Zbl

[33] S. Rosema and R. Tijdeman, The Tribonacci substitution. INTEGERS Electronic Journal of Combinatorial Number Theory 3 (2005) 1553-1732. | MR | Zbl

[34] V.F. Sirvent and B. Solomyak, Pure discrete spectrum for one-dimensional substitution systems of Pisot type. Canad. Math. Bull. 45 (2002) 697-710. | MR | Zbl

[35] V.F. Sirvent and Y. Wang, Self-affine tiling via substitution dynamical systems and Rauzy fractals. Pacific J. Math. 206 (2002) 465-485. | MR | Zbl

[36] W.P. Thurston, Groups, tilings and finite state automata. Summer 1989 AMS Colloquium Lectures (1989).

[37] L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) S787-S805. | MR | Zbl