Complexity and special factors

被引：129

作者：

Cassaigne, J

机构：

来源：

BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN | 1997年 / 4卷 / 01期

关键词：

subword complexity; special factors; substitutive sequences;

D O I：

10.36045/bbms/1105730624

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Among the factors of an infinite sequence on a finite alphabet, some elements have a particular importance: special and bispecial factors. We show how they can be used to compute the complexity of sequences, i.e. the number of factors with a-given length, and to prove that certain functions are obtainable as sequence complexity whereas other functions are not.

引用

页码：67 / 88

页数：22

共 14 条

[1]

Allouche J.-P., 1994, B BELG MATH SOC, V1, P133

[2]

ALLOUCHE JP, 1993, JOURNEES MONTOISES B

[3]

ARNOUX P, 1991, B SOC MATH FRANCE, V199, P199

[4] ENUMERATION OF FACTORS IN THE THUE-MORSE WORD [J].

BRLEK, S .

DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) :83-96

[5]

CASSAIGNE J, 1996, DEV LANGUAGE THEORY

[6]

Cassaigne J., 1994, THESIS PARIS 6

[7]

CASSAIGNE J, 1993, LECT NOTES COMPUT SC, V665, P216

[8] CONSTRUCTIONS OF STRICTLY ERGODIC SYSTEMS .1. GIVEN ENTROPY [J].

GRILLENBERGER, C .

ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1973, 25 (04) :323-334

[9]

MIGNOSI F, 1993, LECT NOTES COMPUT SC, V700

[10]

MOSSE B, 1993, IN PRESS NOTIONS REC

← 1 2 →