Recognizability of substitutions and complexity of automatic sequences

被引:62
作者
Mosse, B [1 ]
机构
[1] LAB MATH DISCRETES,UPR 9016,CNRS,F-13288 MARSEILLE 9,FRANCE
来源
BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE | 1996年 / 124卷 / 02期
关键词
D O I
10.24033/bsmf.2283
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We first recall some notions and one theorem of recognizability about infinite words fixed points of primitive substitutions. When the length of the substitution is constant equal to q, we study the complexity function p(n) of the fixed point u, which is the number of factors of u of length n. We give a method to compute p(n) with linear recurrence formulas and we prove that the sequence (p(n + 1) - p(n))(n is an element of N) is q-automatic.
引用
收藏
页码:329 / 346
页数:18
相关论文
共 10 条
[1]   THE RING OF K-REGULAR SEQUENCES [J].
ALLOUCHE, JP ;
SHALLIT, J .
THEORETICAL COMPUTER SCIENCE, 1992, 98 (02) :163-197
[2]  
ALLOUCHE JP, COMPLEXITE SUITES IN
[3]  
CHRISTOL G, 1980, B SOC MATH FR, V108, P401
[4]  
DEKKING FM, 1980, THESIS NIJMEGEN
[5]  
GABRIEL P, COMMUNICATION
[6]  
HOST B, 1986, ERGOD THEOR DYN SYST, V6, P529
[7]  
Martin J. C., 1973, Mathematical Systems Theory, V7, P73, DOI 10.1007/BF01824809
[8]   POWER OF WORDS AND RECOGNIZABILITY OF FIXED-POINTS OF A SUBSTITUTION [J].
MOSSE, B .
THEORETICAL COMPUTER SCIENCE, 1992, 99 (02) :327-334
[9]  
QUEFFELEC M, 1987, LECT NOTES MATH, V1294
[10]  
TAPSOBA T, 1987, THESIS AIX MARSEILLE