Characterization of N-ecritures and application to the study of sequences of n+cste complexity

被引：16

作者：

Didier, G ^{[1
]}

机构：

[1] CNRS, UPR 9016, Inst Math Luminy, F-13288 Marseille 9, France

来源：

THEORETICAL COMPUTER SCIENCE | 1999年 / 215卷 / 1-2期

关键词：

D O I：

10.1016/S0304-3975(97)00122-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We call N-ecriture the transformation on words which consists on shifting a window of length N along a word and recoding by associating at each factor of length N a new letter. We give a complete characterisation of the words obtained by this transformation and describe a method to get a particular antecedent. Finally we apply previous results to give a new description of sequences which contain n + c(st) different subwords of length n for n great enough. In particular, we explain relations between these sequences and sturmian sequences. (C) 1999-Elsevier Science B.V. All rights reserved.

引用

页码：31 / 49

页数：19

共 11 条

[1]

ALESSANDRI P, 1996, THESIS U AIX MARSEIL

[2]

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

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

[4]

BERSTEL J, DLT 95

[5] Complexity and special factors [J].

Cassaigne, J .

BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 1997, 4 (01) :67-88

[6]

Ferenczi S., 1997, C MATH, V73, P35

[7]

FERENCZI S, 1995, TRANSCENDENCE NUMBER

[8]

HEDLUND GA, 1938, AM J MATH, V60, P815

[9]

HEDLUND GA, 1940, AM J MATH, V62, P287

[10]

MOSSE B, 1996, B SOC MATH FRANCE, V124, P101

← 1 2 →