The critical exponent of the Arshon words

Dalia Krieger

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 1, page 139-150
  • ISSN: 0988-3754

Abstract

top
Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.

How to cite

top

Krieger, Dalia. "The critical exponent of the Arshon words." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 139-150. <http://eudml.org/doc/250792>.

@article{Krieger2010,
abstract = { Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1. },
author = {Krieger, Dalia},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Arshon words; critical exponent.; critical exponent},
language = {eng},
month = {2},
number = {1},
pages = {139-150},
publisher = {EDP Sciences},
title = {The critical exponent of the Arshon words},
url = {http://eudml.org/doc/250792},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Krieger, Dalia
TI - The critical exponent of the Arshon words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 139
EP - 150
AB - Generalizing the results of Thue (for n = 2) [Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1–67] and of Klepinin and Sukhanov (for n = 3) [Discrete Appl. Math. 114 (2001) 155–169], we prove that for all n ≥ 2, the critical exponent of the Arshon word of order n is given by (3n–2)/(2n–2), and this exponent is attained at position 1.
LA - eng
KW - Arshon words; critical exponent.; critical exponent
UR - http://eudml.org/doc/250792
ER -

References

top
  1. S.E. Arshon, A proof of the existence of infinite asymmetric sequences on n symbols. Matematicheskoe Prosveshchenie (Mathematical Education)2 (1935) 24–33 (in Russian). Available electronically at .  URIhttp://ilib.mccme.ru/djvu/mp1/mp1-2.htm
  2. S.E. Arshon, A proof of the existence of infinite asymmetric sequences on n symbols. Mat. Sb.2 (1937) 769–779 (in Russian, with French abstract).  
  3. J. Berstel, Mots sans carré et morphismes itérés. Discrete Math.29 (1979) 235–244.  Zbl0444.20050
  4. J. Berstel, Axel Thue's papers on repetitions in words: a translation. Publications du Laboratoire de Combinatoire et d'Informatique Mathématique 20, Université du Québec à Montréal (1995).  
  5. J.D. Currie, No iterated morphism generates any Arshon sequence of odd order. Discrete Math.259 (2002) 277–283.  Zbl1011.68069
  6. S. Kitaev, Symbolic sequences, crucial words and iterations of a morphism. Ph.D. thesis, Göteborg, Sweden (2000).  
  7. S. Kitaev, There are no iterative morphisms that define the Arshon sequence and the σ-sequence. J. Autom. Lang. Comb.8 (2003) 43–50.  Zbl1064.68053
  8. A.V. Klepinin and E.V. Sukhanov, On combinatorial properties of the Arshon sequence. Discrete Appl. Math.114 (2001) 155–169.  Zbl0995.68506
  9. P. Séébold, About some overlap-free morphisms on a n-letter alphabet. J. Autom. Lang. Comb.7 (2002) 579–597.  Zbl1095.68090
  10. P. Séébold, On some generalizations of the Thue–Morse morphism. Theoret. Comput. Sci.292 (2003) 283–298.  Zbl1064.68079
  11. A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. Mat. Nat. Kl.1 (1912) 1–67.  Zbl44.0462.01
  12. N.Ya. Vilenkin, Formulas on cardboard. Priroda6 (1991) 95–104 (in Russian). English summary available at , review no. MR1143732.  URIhttp://www.ams.org/mathscinet/index.html

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.