Counting bordered and primitive words with a fixed weight

被引：6

作者：

Harju, T ^{[1
]}

Nowotka, D

机构：

[1] Univ Turku, Turku Ctr Comp Sci, Dept Math, FIN-20014 Turku, Finland

[2] Univ Stuttgart, Inst Formal Methods Comp Sci, D-70569 Stuttgart, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 340卷 / 02期

关键词：

combinatorics on words; borders; primitive words; Mobius function;

D O I：

10.1016/j.tcs.2005.03.040

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A word w is primitive if it is not a proper power of another word, and w is unbordered if it has no prefix that is also a suffix of w. We study the number of primitive and unbordered words w with a fixed weight, that is, words for which the Parikh vector of w is a fixed vector. Moreover, we estimate the number of words that have a unique border. (c) 2005 Elsevier B.V All rights reserved.

引用

页码：273 / 279

页数：7

共 7 条

[1]

HARBORTH H, 1974, J REINE ANGEW MATH, V271, P139

[2]

LOTHAIRE M, 1983, COMBINATORIES WORDS, V17

[3] BIFIX-FREE SEQUENCES [J].

NIELSEN, PT .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1973, 19 (05) :704-706

[4] On the language of primitive words [J].

Petersen, H .

THEORETICAL COMPUTER SCIENCE, 1996, 161 (1-2) :141-156

[5] ENUMERATION OF BORDERED WORDS - LE-LANGAGE-DE-LA-VACHE-QUI-RIT [J].

REGNIER, M .

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS, 1992, 26 (04) :303-317

[6]

SIMON I, 1994, LECT NOTES COMPUTER, V812, P386

[7]

SLOANE NJA, LINE ENCY INTEGR SEQ

← 1 →