## The ring of $$k$$-regular sequences.(English)Zbl 0774.68072

Summary: [See also the review of the preliminary version in Zbl 0742.11012.]
The automatic sequence is the central concept at the intersection of formal language theory and number theory. It was introduced by A. Cobham (1969, 1972), and has been extensively studied by G. 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 $$\mathbb{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 $$\mathbb{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. 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.

### MSC:

 68Q45 Formal languages and automata 11B83 Special sequences and polynomials 11B85 Automata sequences 16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras) 68R15 Combinatorics on words

Zbl 0742.11012

ALGOL 60
Full Text: