Lyndon words and singular factors of sturmian words

被引：18

作者：

Melançon, G ^{[1
]}

机构：

[1] Univ Bordeaux 1, UMR 5800 CNRS, LaBRI, F-33405 Talence, France

来源：

THEORETICAL COMPUTER SCIENCE | 1999年 / 218卷 / 01期

关键词：

Lyndon words; sturmian words; singular words;

D O I：

10.1016/S0304-3975(98)00249-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Two different factorizations of the Fibonacci infinite word were given independently in Wen and Wen (1994) and Melancon (1996). In a certain sense, these factorizations reveal a selfsimilarity property of the Fibonacci word. We first describe the intimate links between these two factorizations. We then propose a generalization to characteristic sturmian words. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：41 / 59

页数：19

共 10 条

[1] Sturmian words, Lyndon words and trees
Berstel, J
deLuca, A
[J]. THEORETICAL COMPUTER SCIENCE, 1997, 178 (1-2) : 171 - 203
[2] BERSTEL J, 1996, IN PRESS RECENT RESU
[3] FREE DIFFERENTIAL CALCULUS .4. THE QUOTIENT GROUPS OF THE LOWER CENTRAL SERIES
CHEN, KT
FOX, RH
LYNDON, RC
[J]. ANNALS OF MATHEMATICS, 1958, 68 (01) : 81 - 95
[4] DUVAL JP, 1983, J ALGORITHM, V4, P363, DOI 10.1016/0196-6774(83)90017-2
[5] Lothaire M., 1983, Combinatorics on Words
[6] Viennot factorization of infinite words
Melancon, G
[J]. INFORMATION PROCESSING LETTERS, 1996, 60 (02) : 53 - 57
[7] MELANCON G, IN PRESS 8 INT C FOR
[8] MELANCON G, 1996, STACS 96, V1046, P147
[9] INFINITE LYNDON WORDS
SIROMONEY, R
MATHEW, L
DARE, VR
SUBRAMANIAN, KG
[J]. INFORMATION PROCESSING LETTERS, 1994, 50 (02) : 101 - 104
[10] WEN ZX, 1994, EUR J COMBIN, V15, P587

← 1 →