AVERAGE COST OF DUVALS ALGORITHM FOR GENERATING LYNDON WORDS

被引：16

作者：

BERSTEL, J ^{[1
]}

POCCHIOLA, M ^{[1
]}

机构：

[1] ECOLE NORMALE SUPER,LIENS,CNRS,URA 1327,F-75230 PARIS 05,FRANCE

来源：

THEORETICAL COMPUTER SCIENCE | 1994年 / 132卷 / 1-2期

关键词：

D O I：

10.1016/0304-3975(94)00013-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The average cost of Duval's algorithm for generating all Lyndon words up to a given length in lexicographic order is proved to be asymptotically equal to (q + 1)/(q - 1), where q is the size of the underlying alphabet. In particular, the average cost is independent of the length of the words generated. A precise evaluation of the constants is also given.

引用

页码：415 / 425

页数：11

共 15 条

[1] LEXICOGRAPHICALLY LEAST CIRCULAR SUBSTRINGS [J].

BOOTH, KS .

INFORMATION PROCESSING LETTERS, 1980, 10 (4-5) :240-242

[2]

CHAR BW, 1991, MAPLE 5 LANGUAGE REF

[3]

DUVAL JP, 1983, J ALGORITHM, V4, P363, DOI 10.1016/0196-6774(83)90017-2

[4] GENERATION OF A SECTION OF CONJUGATION CLASSES AND A TREE OF LYNDON WORDS OF LIMITED LENGTH [J].

DUVAL, JP .

THEORETICAL COMPUTER SCIENCE, 1988, 60 (03) :255-283

[5] SINGULARITY ANALYSIS OF GENERATING-FUNCTIONS [J].

FLAJOLET, P ;

ODLYZKO, A .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (02) :216-240

[6]

Lidl R., 1984, FINITE FIELDS

[7]

Lothaire M., 1983, COMBINATORICS WORDS

[8] ON BURNSIDES PROBLEM [J].

LYNDON, RC .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1954, 77 (SEP) :202-215

[9]

Reutenauer C., 1993, FREE LIE ALGEBRAS

[10] GENERATING NECKLACES [J].

RUSKEY, F ;

SAVAGE, C ;

WANG, TMY .

JOURNAL OF ALGORITHMS, 1992, 13 (03) :414-430

← 1 2 →