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.  Zbl1059.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.  Zbl1121.68089
  3. P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin8 (2001) 181–207.  Zbl1007.37001
  4. P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991) 199–215.  Zbl0789.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).  Zbl1017.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.  Zbl1017.11006
  7. M. Barge and B. Diamond, Proximality in Pisot Tiling Spaces. Fund. Math.194 (2007) 191–238.  Zbl1115.37010
  8. M. Barge and J. Kwapisz, Geometric theory of unimodular Pisot substitutions. Amer. J. Math.128 (2006) 1219–1282.  Zbl1152.37011
  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.  Zbl1068.37005
  13. V. Canterini and A. Siegel, Geometric representation of substitutions of Pisot type. Trans. Amer. Math. Soc.353 (2001) 5121–5144.  Zbl1142.37302
  14. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble)50 (2000) 1265–1276.  Zbl1004.37008
  15. A. de Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett.12 (1981) 193–195.  Zbl0468.20049
  16. X. Droubay, Palindromes in the Fibonacci word. Inform. Process. Lett.55 (1995) 217–221.  Zbl1004.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.  Zbl0981.68126
  18. F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998) 89–101.  Zbl0895.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.  Zbl1044.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.  
  21. C. Frougny, Confluent linear numeration systems. Theoret. Comput. Sci.106 (1992) 183–219.  Zbl0787.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.  Zbl0625.28011
  23. S. Ito and H. Rao, Atomic surfaces, tilings and coincidences I. Irreducible case. Israel J. Math.153 (2006) 129–155.  Zbl1143.37013
  24. J. Justin and G. Pirillo, On a characteristic property of Arnoux-Rauzy sequences. RAIRO-Theor. Inf. Appl.36 (2002) 385–388.  Zbl1060.68094
  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).  Zbl1001.68093
  27. B.F. Martensen, Generalized balanced pair algorithm. Topology Proc.28 (2004) 163–178.  Zbl1077.37018
  28. W. Parry, On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar.11 (1960) 401–416.  Zbl0099.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 Mathematics1794 (2002).  Zbl1014.11015
  30. M. Queffélec, Substitution dynamical systems–spectral analysis. Lecture Notes in Mathematics 1294 (1987).  Zbl0642.28013
  31. R.N. Risley and L.Q. Zamboni, A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith.95 (2000) 167–184.  Zbl0953.11007
  32. A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar.8 (1957) 477–493.  Zbl0079.08901
  33. S. Rosema and R. Tijdeman, The Tribonacci substitution. INTEGERS Electronic Journal of Combinatorial Number Theory3 (2005) 1553–1732.  Zbl1099.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.  Zbl1038.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.  Zbl1048.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 Stevin10 (2003) S787–S805.  Zbl1070.68129

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.