The Ring of k-Regular Sequences
The Ring of k-Regular Sequences
复制标题
DOI：
10.1007/3-540-52282-4_28
复制
发表时间：
1990-02
影响因子：
2
通讯作者：
J. Allouche;J. Shallit
中科院分区：
文献类型：
--
作者：
J. Allouche;J. Shallit
自动序列是形式语言理论和数论交叉的核心概念。它是由科巴姆提出的，克里斯托尔、卡梅、门代·S、法兰西和劳兹等作家都对其进行了广泛的研究。然而，由于自动机序列的取值范围是有限的，其描述能力是非常有限的.本文将自动机序列的概念推广到这样的情形，即自动机序列可以取值于(可能是无限的)环R，我们称这种序列为k-正则序列.(如果R是有限的，作为特例，我们得到自动序列。)我们从数值分析、拓扑学、数论、组合学、算法分析和分形论等方面给出了许多K-正则序列的例子来支持这一论点，并研究了K-正则序列的封闭性。我们证明了K-正则序列的集合在逐项加法和卷积运算下形成一个环。我们证明了Howk-正则序列与ℤ-有理形式级数相关。给出了k-正则序列的机器模型。我们证明了所有k-正则序列是可以快速计算的，让模式序列EP(N)计算模式在n的基-k展开中出现的次数。Morton和Mourant证明了ℤ上的每个序列都有作为模式序列和的唯一展开式。我们证明了这种“傅立叶”展开映射正则序列为正则序列。特别地，Fep(An+b)展开式中的系数形成了AK-自动序列。
Theautomatic sequenceis the central concept at the intersection of formal language theory and number theory. It was introduced by Cobham, and has been extensively studied by Christol, Kamae, Mendès France and Rauzy, and other writers. Since the range of an automatic sequence is finite, however, their descriptive power is severely limited.In this paper, we generalize the concept of automatic sequence to the case where the sequence can take its values in a (possibly infinite) ringR; we call such sequencesk-regular. (IfRis finite, we obtain automatic sequences as a special case.) We argue thatk-regular sequences provide a good framework for discussing many “naturally-occurring” sequences, and we support this contention by exhibiting many examples ofk-regular sequences from numerical analysis, topology, number theory, combinatorics, analysis of algorithms, and the theory of fractals.We investigate the closure properties ofk-regular sequences. We prove that the set ofk-regular sequences forms a ring under the operations of term-by-term addition and convolution. Hence the set of associated formal power series inR[[X]] also forms a ring.We show howk-regular sequences are related to ℤ-rational formal series. We give a machine model for thek-regular sequences. We prove that allk-regular sequences can be computed quickly.Let thepattern sequence ep (n)count the number of occurrences of the patternPin the base-kexpansion ofn. Morton and Mourant showed that every sequence over ℤ has a unique expansion as sum of pattern sequences. We prove that this “Fourier” expansion mapsk-regular sequences tok-regular sequences. In particular, the coefficients in the expansion ofep(an+b)form ak-automatic sequence.