THE RING OF K-REGULAR SEQUENCES

The automatic sequence is the central concept at the intersection of formal language theory and number theory. It was introduced by Cobham (1969, 1972), and has been extensively studied by Christol et al. (1980) and other writers. Since the range of automatic sequences 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) ring R; we call such sequences k-regular. (When R is finite, we obtain automatic sequences as a special case.) We argue that k-regular sequences provide a good framework for discussing many "naturally occurring" sequences, and we support this contention by exhibiting many examples of k-regular sequences from numerical analysis, topology, number theory, combinatorics, analysis of algorithms, and the theory of fractals. We investigate the closure properties of k-regular sequences. We prove that the set of k-regular sequences forms a ring under the operations of term-by-term addition and convolution. Hence, the set of associated formal power series in R[[X]] also forms a ring. We show how k-regular sequences are related to Z-rational formal series. We give a machine model for the k-regular sequences. We prove that all k-regular sequences can be computed quickly. Let the pattern sequence e(P)(n) count the number of occurrences of the pattern P in the base-k expansion of n. Morton and Mourant (1989) showed that every sequence over Z has a unique expansion as a sum of pattern sequences. We prove that this "Fourier" expansion maps k-regular sequences to k-regular sequences. [This can be viewed as a generalization of results of Choffrut and Schutzenberger(1988), and previous results of Allouche et al. (1992)]. In particular, the coefficients in the expansion of e(P)(an + b) form a k-automatic sequence.(~)Many natural examples and some open problems are given.