Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words

Ondřej Turek

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 3, page 313-337
  • ISSN: 0988-3754

Abstract

top
A word u defined over an alphabet 𝒜 is c-balanced (c∈ ) if for all pairs of factors v, w of u of the same length and for all letters a∈ 𝒜 , the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet 𝒜 = {L, S, M} and a class of substitutions ϕ p defined by ϕ p (L) = LpS, ϕ p (S) = M, ϕ p (M) = Lp–1S where p> 1. We prove that the fixed point of ϕ p , formally written as ϕ p (L), is 3-balanced and that its Abelian complexity is bounded above by the value 7, regardless of the value of p. We also show that both these bounds are optimal, i.e. they cannot be improved.

How to cite

top

Turek, Ondřej. "Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words." RAIRO - Theoretical Informatics and Applications 44.3 (2010): 313-337. <http://eudml.org/doc/250799>.

@article{Turek2010,
abstract = { A word u defined over an alphabet $\mathcal A$ is c-balanced (c∈$\mathbb N$) if for all pairs of factors v, w of u of the same length and for all letters a∈$\mathcal A$, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet $\mathcal A$ = \{L, S, M\} and a class of substitutions $\varphi_p$ defined by $\varphi_p$(L) = LpS, $\varphi_p$(S) = M, $\varphi_p$(M) = Lp–1S where p> 1. We prove that the fixed point of $\varphi_p$, formally written as $\varphi_p^\infty$(L), is 3-balanced and that its Abelian complexity is bounded above by the value 7, regardless of the value of p. We also show that both these bounds are optimal, i.e. they cannot be improved. },
author = {Turek, Ondřej},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Balance property; Abelian complexity; substitution; ternary word; balance property},
language = {eng},
month = {10},
number = {3},
pages = {313-337},
publisher = {EDP Sciences},
title = {Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words},
url = {http://eudml.org/doc/250799},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Turek, Ondřej
TI - Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/10//
PB - EDP Sciences
VL - 44
IS - 3
SP - 313
EP - 337
AB - A word u defined over an alphabet $\mathcal A$ is c-balanced (c∈$\mathbb N$) if for all pairs of factors v, w of u of the same length and for all letters a∈$\mathcal A$, the difference between the number of letters a in v and w is less or equal to c. In this paper we consider a ternary alphabet $\mathcal A$ = {L, S, M} and a class of substitutions $\varphi_p$ defined by $\varphi_p$(L) = LpS, $\varphi_p$(S) = M, $\varphi_p$(M) = Lp–1S where p> 1. We prove that the fixed point of $\varphi_p$, formally written as $\varphi_p^\infty$(L), is 3-balanced and that its Abelian complexity is bounded above by the value 7, regardless of the value of p. We also show that both these bounds are optimal, i.e. they cannot be improved.
LA - eng
KW - Balance property; Abelian complexity; substitution; ternary word; balance property
UR - http://eudml.org/doc/250799
ER -

References

top
  1. B. Adamczewski, Codages de rotations et phénomènes d'autosimilarité. J. Théor. Nombres Bordeaux14 (2002) 351–386.  
  2. B. Adamczewski, Balances for fixed points of primitive substitutions. Theoret. Comput. Sci.307 (2003) 47–75.  Zbl1059.68083
  3. Ľ. Balková, E. Pelantová and Š. Starosta, Sturmian Jungle (or Garden?) on Multiliteral Alphabets. RAIRO: Theoret. Informatics Appl (to appear).  Zbl1211.68295
  4. Ľ. Balková, E. Pelantová and O. Turek, Combinatorial and Arithmetical Properties of Infinite Words Associated with Quadratic Non-simple Parry Numbers. RAIRO: Theoret. Informatics Appl.413 (2007) 307–328.  Zbl1144.11009
  5. V. Berthé and R. Tijdeman, Balance properties of multi-dimensional words. Theoret. Comput. Sci.273 (2002) 197–224.  Zbl0997.68091
  6. J. Cassaigne, Recurrence in infinite words, in Proc. STACS, LNCS Dresden (Allemagne) 2010, Springer (2001) 1–11.  Zbl0976.68524
  7. J. Cassaigne, S. Ferenczi and L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier50 (2000) 1265–1276.  Zbl1004.37008
  8. E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Th.7 (1973) 138–153.  Zbl0256.54028
  9. J. Currie and N. Rampersad, Recurrent words with constant Abelian complexity. Adv. Appl. Math. doi: (2010).  Zbl1222.68126DOI10.1016/j.aam.2010.05.001
  10. S. Fabre, Substitutions et β-systèmes de numération. Theoret. Comput. Sci.137 (1995) 219–236.  Zbl0872.11017
  11. C. Frougny, J.P. Gazeau and J. Krejcar, Additive and multiplicative properties of point-sets based on beta-integers. Theor. Comp. Sci.303 (2003) 491–516.  Zbl1036.11034
  12. K. Klouda and E. Pelantová, Factor complexity of infinite words associated with non-simple Parry numbers. Integers – Electronic Journal of Combinatorial Number Theory (2009) 281–310.  Zbl1193.68201
  13. M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002).  Zbl1001.68093
  14. M. Morse and G.A. Hedlund, Symbolic dynamics. Am. J. Math.60 (1938) 815–866.  Zbl0019.33502
  15. M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian Trajectories. Am. J. Math.62 (1940) 1–42.  Zbl0022.34003
  16. G. Richomme, K. Saari, L. Q. Zamboni, Balance and Abelian Complexity of the Tribonacci word. Adv. Appl. Math.45 (2010) 212–231.  Zbl1203.68131
  17. G. Richomme, K. Saari, L. Q. Zamboni, Abelian Complexity in Minimal Subshifts. J. London Math. Soc. (to appear).  Zbl1211.68300
  18. W. Thurston, Groups, tilings and finite state automata. AMS Colloquium Lecture Notes (1989).  
  19. O. Turek, Balance properties of the fixed point of the substitution associated to quadratic simple Pisot numbers. RAIRO: Theoret. Informatics Appl.41 2 (2007) 123–135.  Zbl1146.68410
  20. L. Vuillon, Balanced words. Bull. Belg. Math. Soc. Simon Stevin10 (2003) 787–805.  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.