代换序列的复杂度理论及相关分形问题

Combined with Fractal Geometry，Number Theory and Combination on Words， we shall research the complexity theory of morphic sequences and its related fractal problems: (1) we shall give a systematic study on the k-abelian and Cyclic complexities of automatic sequences over the alphabet with no less than three letters;(2)we shall study the fractal structure and dimensions of self-similar functions corresponding to different kinds of complexity functions of a class of morphic sequences;(3）starting from regular sequences, we shall investigate the properties of some quasi-linear discrete functions and estimate the dimensions of the fractal functions generated by them。Those problems are not only the intersection of fractal theory,combination on words, theoretical computer science and number theory，but also hot issues of the reseach of the above subjects. These problems are of great theoretical significance.

结合分形几何、数论与词上组合等方法技巧，本项目拟从三个方面去研究代换序列复杂度理论及相关的分形问题：（1）我们将系统深入地研究多字符自动机序列的k-abelian复杂度和Cyclic复杂度；（2）研究代换序列的各种复杂度相对应的自相似函数图像的分形结构及其维数；（3）由正则序列出发，研究拟线性函数的性质以及由其构造的分形函数图像的维数问题。因此本项目将涉及分形几何、词上组合、理论计算科学与数论的交叉，同时也是这些研究方向的热点问题，具有重要的理论意义。

代换序列的研究是词上组合，理论计算科学与及分形几何等领域的重要研究内容，在信号处理、DNA结构分析、形式语言等领域也具有较好的应用前景。本项目旨在从不同的角度开展对代换序列的复杂度进行研究，探索其组合性质与分形结构，该课题具有重要的理论意义。. 我们主要研究了自动机序列的k-abelian复杂度，k-binomial复杂度及其正则性，讨论了拟线性函数诱导的自相似函数图像的分形结构及维数，以及自动机序列的边界序列等问题。研究成果主要包括三个部分：一是给出了拟线性函数的精确定义及其生成的自相似函数图像盒子维数上下界的最佳估计；二是证明了自动机序列的边界序列依旧是自动机的；三是证明了类Cantor序列的2-abelian复杂度的正则性及推广的Thue-Morse序列2-binomial复杂度的周期性。. 通过相关探索及研究，我们完善了自相似函数图像维数理论，发展了自动机序列因子结构的基本理论，丰富了自动机序列复杂度的研究方法。