代换序列的复杂度及相关问题

In this project, we focus on the complexity of morphic sequences and related issues by using the techniques in fractal geometry, combination on words and theory of symbolic space, automaton. (1) Based on the theory of automaton, we study necessary and sufficient conditions such that a class of regular sequences can be generated by the generalized automatons. (2) Using the techniques in combination on words, we investigate the abelian complexity and the k-abelian complexity of some special morphic sequences. (3) Using the techniques in fractal geometry and symbolic space, we research the box dimension and Hausdorff dimension of the fractal functions generated from the running sum of some special morphic sequences.

本项目拟综合运用分形几何、词上组合、自动机和符号空间等数学理论和方法，对代换序列的复杂度及相关问题开展研究。（1）利用自动机理论，拟研究一类正则序列可由某种广义自动机生成的充要条件。(2) 利用词上组合理论，研究几类特殊代换序列的Abel复杂度和k-Abel复杂度。(3) 利用分形几何与符号空间理论，拟研究特殊代换序列的部分和诱导出的分形函数图像的盒维数与Hausdorff维数。

本项目综合运用分形几何、词上组合、自动机和符号空间等数学理论和方法，对代换序列的复杂度及相关问题开展研究。复杂度作为刻画序列复杂程度的指标，复杂度理论在分形几何、动力系统甚至生物信息中都有一定应用。 （1）相对于有限状态自动机，可数状态自动机的研究要困难的多。本项目研究了几类由可数状态自动机生成的序列，我们得到，一类正则序列可以由可数状态自动机来生成。（2）对于Rudin-Shapiro序列，本项目得到其阿贝尔复杂度是2-正则的，并由其阿贝尔复杂度诱导出一个分形函数，还计算出该分形函数的盒子维数，此结果建立了词上组合与分形几何两个分支之间的紧密联系，（3）本项目还研究了著名的Cantor序列的k-阿贝尔复杂度，并得到，对任意的k，Cantor序列的k-阿贝尔复杂度都是3-正则的，这是有关k-阿贝尔序列的正则性问题中的第一个具体且完整的结果。