两字母代换序列复杂度的计算 献给余家荣教授100华诞  

Calculation of the complexities of substitutive sequences over a binary alphabet

作　　者：谭波 文志雄[1] 章逸平[2] Bo Tan;Zhixiong Wen;Yiping Zhang

机构地区：[1]华中科技大学数学与统计学院,武汉430074 [2]武汉大学数学与统计学院,武汉430072

出　　处：《中国科学：数学》2019年第11期1675-1686,共12页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:11431007,11222111和11471130)资助项目

摘　　要：两字母代换序列的复杂度的计算对于等长代换已经解决,然而非等长代换的复杂度计算要复杂得多,此前并没有完全解决.本文讨论一般的可不等长的两字母代换,通过研究几种类型的特殊词,证明只需计算出一些初始值,复杂度可用相应特征多项式的递归公式完全表示出来.We consider the complexities of substitutive sequences over a binary alphabet. By studying various types of special words, we show that, knowing some initial values, its complexity can be completely formulated via a recurrence formula determined by the characteristic polynomial.

关 键 词：代换 特殊词 复杂度 

分 类 号：O1[理学—数学]