Study of irreducible balanced pairs for substitutive languages

Bernat, Julien

Bernat, Julien

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008), p. 663-678 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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.

Publié le : 2008-01-01

MR 2458700 | Zbl 1155.68060

DOI : https://doi.org/10.1051/ita:2007062
Classification: 68R15

@article{ITA_2008__42_4_663_0,
     author = {Bernat, Julien},
     title = {Study of irreducible balanced pairs for substitutive languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {42},
     year = {2008},
     pages = {663-678},
     doi = {10.1051/ita:2007062},
     mrnumber = {2458700},
     zbl = {1155.68060},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2008__42_4_663_0}
}

Bernat, Julien. Study of irreducible balanced pairs for substitutive languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 663-678. doi : 10.1051/ita:2007062. http://gdmltest.u-ga.fr/item/ITA_2008__42_4_663_0/

Bibliographie

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

[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 2290777 | Zbl 1121.68089

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

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

[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 1888763 | Zbl 1017.68147

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

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

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

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

[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 0589.68053

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

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

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

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

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

[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 1819089 | Zbl 0981.68126

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

[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 1709427 | Zbl 1044.46543

[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 1388964 | Zbl 0871.11009

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

[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 873430 | Zbl 0625.28011

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

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

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

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

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

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

[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 1970385 | Zbl 1014.11015

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

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

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

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

[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 1941235 | Zbl 1038.37008

[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 1926787 | Zbl 1048.37015

[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 2073026 | Zbl 1070.68129