Fine and Wilf's theorem for three periods and a generalization of Sturmian words

被引：48

作者：

Castelli, MG ^{[1
]}

Mignosi, F ^{[1
]}

Restivo, A ^{[1
]}

机构：

[1] Univ Palermo, Dipartimento Matemat & Applicaz, I-90123 Palermo, Italy

来源：

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

关键词：

combinatorics on words; periodicity; Euclid's algorithm; Sturmian words;

D O I：

10.1016/S0304-3975(98)00251-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We extend the theorem of Fine and Wilf to words having three periods. We then define the set 3-PER of words of maximal length for which such result does not apply. We prove that the set 3-PER and the sequences of complexity 2n + 1, introduced by Arnoux and Rauzy to generalize Sturmian words, have the same set of factors. (C) 1999 Elsevier Science B.V. All rights reserved.

引用

页码：83 / 94

页数：12

共 20 条

[1]

ARNOUX P, 1994, B SOC MATH FR, V122, P1

[2] 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

[3] Sturmian words, Lyndon words and trees [J].

Berstel, J ;

deLuca, A .

THEORETICAL COMPUTER SCIENCE, 1997, 178 (1-2) :171-203

[4]

Berstel J., 1985, Pure Appl. Math., V117

[5] ALGORITHM AND BOUND FOR GREATEST COMMON DIVISOR OF N INTEGERS [J].

BRADLEY, GH .

COMMUNICATIONS OF THE ACM, 1970, 13 (07) :433-&

[6] SOME COMBINATORIAL PROPERTIES OF STURMIAN WORDS [J].

DELUCA, A ;

MIGNOSI, F .

THEORETICAL COMPUTER SCIENCE, 1994, 136 (02) :361-385

[7] Sturmian words: structure, combinatorics, and their arithmetics [J].

deLuca, A .

THEORETICAL COMPUTER SCIENCE, 1997, 183 (01) :45-82

[8] Standard Sturmian morphisms [J].

deLuca, A .

THEORETICAL COMPUTER SCIENCE, 1997, 178 (1-2) :205-224

[9] UNIQUENESS THEOREMS FOR PERIODIC FUNCTIONS [J].

FINE, NJ ;

WILF, HS .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 16 (01) :109-&

[10]

Graham RL., 1988, Concrete Mathematics

← 1 2 →