EPISTURMIAN WORDS: A SURVEY

被引：55
作者：
Glen, Amy [1 ,2 ]
Justin, Jacques [3 ]
机构：
[1] Univ Quebec, LaCIM, Montreal, PQ H3C 3P8, Canada
[2] Reykjavik Univ, Math Inst, IS-103 Reykjavik, Iceland
[3] Univ Paris Diderot, LIAFA, F-75205 Paris 13, France
来源：
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2009年 / 43卷 / 03期
关键词：
Combinatorics on words; episturmian words; Arnoux-Rauzy sequences; Sturmian words; episturmian morphisms; STURMIAN WORDS; SYMBOLIC DYNAMICS; PALINDROMIC COMPLEXITY; INFINITE WORDS; SEQUENCES; MORPHISMS; THEOREM; POWERS; REPRESENTATION; TRANSCENDENCE;
D O I：
10.1051/ita/2009003
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we survey the rich theory of infinite episturmian words which generalize to any finite alphabet, in a rather resembling way, the well-known family of Sturmian words on two letters. After recalling definitions and basic properties, we consider episturmian morphisms that allow for a deeper study of these words. Some properties of factors are described, including factor complexity, palindromes, fractional powers, frequencies, and return words. We also consider lexicographical properties of episturmian words, as well as their connection to the balance property, and related notions such as finite episturmian words, Arnoux-Rauzy sequences, and "episkew words" that generalize the skew words of Morse and Hedlund.
引用
收藏
页码：403 / 442
页数：40
相关论文
共 117 条
[11]  
[Anonymous], 2002, LECT NOTES MATH, DOI DOI 10.1007/B13861
[12]   EFFICIENT DETECTION OF QUASIPERIODICITIES IN STRINGS [J].
APOSTOLICO, A ;
EHRENFEUCHT, A .
THEORETICAL COMPUTER SCIENCE, 1993, 119 (02) :247-265
[13]  
APOSTOLICO A, 2002, HDB MASSIVE DATA SET, V4
[14]   GEOMETRIC REPRESENTATION OF SEQUENCES OF COMPLEXITY 2N+1 [J].
ARNOUX, P ;
RAUZY, G .
BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 1991, 119 (02) :199-215
[15]   Pisot substitutions and Rauzy fractals [J].
Arnoux, P ;
Ito, S .
BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2001, 8 (02) :181-207
[16]  
BARYSHNIKOV Y, 1995, COMMUN MATH PHYS, V174, P43, DOI 10.1007/BF02099463
[17]   Recent results on extensions of Sturmian words [J].
Berstel, J .
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2002, 12 (1-2) :371-385
[18]   Coding rotations on intervals [J].
Berstel, J ;
Vuillon, L .
THEORETICAL COMPUTER SCIENCE, 2002, 281 (1-2) :99-107
[19]  
Berstel J., 1999, JEWELS ARE FOREVER, P287
[20]  
Berthé V, 2005, CONTEMP MATH, V385, P333
12345678910