| 两字母代换序列复杂度的计算 献给余家荣教授100华诞 |
| |
| 引用本文： | 谭波,文志雄,章逸平.两字母代换序列复杂度的计算 献给余家荣教授100华诞[J].中国科学:数学,2019(11):1675-1686. |
| |
| 作者姓名： | 谭波 文志雄 章逸平 |
| |
| 作者单位： | 华中科技大学数学与统计学院;武汉大学数学与统计学院 |
| |
| 基金项目： | 国家自然科学基金(批准号:11431007,11222111和11471130)资助项目 |
| |
| 摘 要： | 两字母代换序列的复杂度的计算对于等长代换已经解决,然而非等长代换的复杂度计算要复杂得多,此前并没有完全解决.本文讨论一般的可不等长的两字母代换,通过研究几种类型的特殊词,证明只需计算出一些初始值,复杂度可用相应特征多项式的递归公式完全表示出来.
|
| 关 键 词： | 代换 特殊词 复杂度 |
Calculation of the complexities of substitutive sequences over a binary alphabet |
| |
| Bo Tan,Zhixiong Wen,Yiping Zhang.Calculation of the complexities of substitutive sequences over a binary alphabet[J].Scientia Sinica Mathemation,2019(11):1675-1686. |
| |
| Authors: | Bo Tan Zhixiong Wen Yiping Zhang |
| |
| Abstract: | 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. |
| |
| Keywords: | substitution special word complexity |
| 本文献已被 CNKI 维普 等数据库收录！ |
