自相似序列的因子谱性质及相关分形结构

The factor spectra properties and related fractal structures of the self-similar sequences will be studied in this proposal. We mainly study two problems: (1) The traditional theory of combinatorics on words studies whether a word appears in a sequence as a factor, the frequencies of the factors, and so on. Since it lacks the tool, we cannot study the positions where the factors locate, but this property plays an important role in the factor structure. We will study the factors which satisfy some combinatorics property, and introduce the notion of spectra, which considers factor and the position where the factor appears as two variables. That will give a new idea and some new methods for studying in this area. For studying the positions where the factors appears, we introduce some tools, such as the gap sequences, kernel and envelope words of a factor, reflexivity. The properties of them are various in different self-similar sequences. (2) The fractal structure derived from the positions of factors, gives a new relation between the self-similar sequence and fractal. As an interesting application, by the chain structure and the tree structure we founded, we can solve a problem in theoretical of computer science: how many factors in a certain type occur in a given block of sequence. This project is at the intersection of fractal theory, combinatorics on words, and theoretical of computer science. In this project, we wish to obtain some rather general results.

本项目的研究对象是自相似序列的因子谱性质以及相关的分形结构。(1)传统的词上组合性质仅研究满足某一性质的某个因子是否出现、因子出现的频率等性质。但由于缺乏工具，没有研究因子逐次出现的位置这一重要性质。本项目研究满足某一组合性质的因子性质：同时考虑因子与位置两个变量，可以获得诸如任意因子在序列中每次出现的位置、相互关系等信息，称为因子谱性质。它提供了全新的研究视角。为了研究因子谱性质，我们引入了间隔序列、核词、包络词、自反性等有力的工具，它们在不同的自相似序列中表现出不同的作用。(2)因子位置的分形结构，建立了自相似序列与分形的新联系。作为一个重要应用，利用我们已经发现的链结构和树结构，可以解决理论计算机领域广泛关注的因子计数问题，即给定属性的因子在给定序列片段中出现的次数。本项目属于分形、词上组合和理论计算机的交叉领域。通过本项目，我们希望在现有研究基础上获得一般性结论。