Study of irreducible balanced pairs for substitutive languages

Julien Bernat

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 4, page 663-678
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Bernat, Julien. "Study of irreducible balanced pairs for substitutive languages." RAIRO - Theoretical Informatics and Applications 42.4 (2008): 663-678. <http://eudml.org/doc/250352>.

@article{Bernat2008,
abstract = { Let $\mathcal\{L\}$ be a language. A balanced pair (u,v) consists of two words u and v in $\mathcal\{L\}$ 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. },
author = {Bernat, Julien},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Substitutive languages; balanced pairs; algorithm on words.; substitutive languages; algorithm on words},
language = {eng},
month = {1},
number = {4},
pages = {663-678},
publisher = {EDP Sciences},
title = {Study of irreducible balanced pairs for substitutive languages},
url = {http://eudml.org/doc/250352},
volume = {42},
year = {2008},
}

TY - JOUR
AU - Bernat, Julien
TI - Study of irreducible balanced pairs for substitutive languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/1//
PB - EDP Sciences
VL - 42
IS - 4
SP - 663
EP - 678
AB - Let $\mathcal{L}$ be a language. A balanced pair (u,v) consists of two words u and v in $\mathcal{L}$ 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.
LA - eng
KW - Substitutive languages; balanced pairs; algorithm on words.; substitutive languages; algorithm on words
UR - http://eudml.org/doc/250352
ER -

References

top
  1. B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci.307 (2003) 47–75.  
  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.  
  3. P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 181–207.  
  4. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  
  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).  
  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.  
  7. M. Barge and B. Diamond, Proximality in Pisot Tiling Spaces. Fund. Math.194 (2007) 191–238.  
  8. M. Barge and J. Kwapisz, Geometric theory of unimodular Pisot substitutions. Amer. J. Math.128 (2006) 1219–1282.  
  9. J. Bernat, Symmetrized β-integers (2006) Submitted.  
  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).  
  12. V. Berthé and R. Tijdeman, Lattices and multi-dimensional words. Theoret. Comput. Sci.319 (2004) 177–202.  
  13. V. Canterini and A. Siegel, Geometric representation of substitutions of Pisot type. Trans. Amer. Math. Soc.353 (2001) 5121–5144.  
  14. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble)50 (2000) 1265–1276.  
  15. A. de Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett.12 (1981) 193–195.  
  16. X. Droubay, Palindromes in the Fibonacci word. Inform. Process. Lett.55 (1995) 217–221.  
  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.  
  18. F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101.  
  19. F. Durand, B. Host and C. Skau, Substitutional dynamical systems, Bratteli diagrams and dimension groups. Ergod. Theor. Dyn. Syst.19 (1999) 953–993.  
  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.  
  21. C. Frougny, Confluent linear numeration systems. Theoret. Comput. Sci.106 (1992) 183–219.  
  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.  
  23. S. Ito and H. Rao, Atomic surfaces, tilings and coincidences I. Irreducible case. Israel J. Math.153 (2006) 129–155.  
  24. J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl.36 (2002) 385–388.  
  25. A.N. Livshits, Some examples of adic transformations and automorphisms of substitutions. Selecta Math. Soviet.11 (1992) 83–104. Selected translations.  
  26. M. Lothaire, Algebraic Combinatorics On Words. Cambridge University Press (2002).  
  27. B.F. Martensen, Generalized balanced pair algorithm. Topology Proc.28 (2004) 163–178.  
  28. W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960) 401–416.  
  29. N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatoric, edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Lecture Notes in Mathematics1794 (2002).  
  30. M. Queffélec, Substitution dynamical systems–spectral analysis. Lecture Notes in Mathematics 1294 (1987).  
  31. R.N. Risley and L.Q. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith.95 (2000) 167–184.  
  32. A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar.8 (1957) 477–493.  
  33. S. Rosema and R. Tijdeman, The Tribonacci substitution. INTEGERS Electronic Journal of Combinatorial Number Theory3 (2005) 1553–1732.  
  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.  
  35. V.F. Sirvent and Y. Wang, Self-affine tiling via substitution dynamical systems and Rauzy fractals. Pacific J. Math.206 (2002) 465–485.  
  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 Stevin10 (2003) S787–S805.  

NotesEmbed ?

top

You must be logged in to post comments.