Abstract
The automatic sequence is 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) ring R; we call such sequences k-regular. (If 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 ℤ-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 ep (n) count the number of occurrences of the pattern P in the base-k expansion of n. Morton and Mourant showed that every sequence over ℤ has a unique expansion as 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 ep(an+b) form a k-automatic sequence.
Research supported in part by “PICS: Théorie des nombres et ordinateurs”
Research supported in part by NSF Grant CCR-8817400, the Wiscconsin Alumni Research Foundation, and a Walter Burke award.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.-P. Allouche, Automates finis en théorie des nombres, Expo. Math. 5 (1987), 239–266.
J.-P. Allouche, P. Morton, and J. Shallit, Pattern spectra, substring enumeration, and automatic sequences, preprint.
N. G. de Bruijn, Some direct decompositions of the set of integers, Math. Tables Aids Comput. 18 (1964), 537–546.
A. Blanchard and M. Mendès France, Symétrie et transcendance, Bull. Sci. Math. 106 (1982), 325–335.
J. Berstel and C. Reutenauer, Rational series and their languages, Springer-Verlag, 1988.
S. Brlek, Enumeration of factors in the Thue-Morse word, Disc. Appl. Math. 24 (1989), 83–96.
G. Christol, T. Kamae, M. Mendès France and G. Rauzy, Suites algébriques, automates et substitutions, Bull. Soc. Math. France 108 (1980), 401–419.
A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972), 164–192.
J. Coquet, A summation formula related to the binary digits, Invent. Math. 73 (1983), 107–115.
J. C. van der Corput, Verteilungsfunktionen, Proc. Ned. Akad. v. Wet. 38 (1935), 813–821.
C. Choffrut and M. P. Schützenberger, Counting with rational functions, Theor. Comput. Sci. 58 (1988), 81–101.
M. Dekking, M. Mendès France, and A. van der Poorten, FOLDS!, Math. Intell. 4 (1982), 130–138; 173–195.
N. J. Fine, Binomial coefficients modulo a prime, Amer. Math. Monthly 54 (1947), 589–592.
P. Flajolet and L. Ramshaw, A note on Gray code and odd-even merge, SIAM J. Comput. 9 (1980), 142–158.
H. W. Gould, Exponential binomial coefficient series, Technical Report 4, Department of Mathematics, W. Virginia Univ., September 1961.
E. Gilbert, Gray codes and paths on the n-cube, Bell Sys. Tech. J. 37 (1958), 815–826.
R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley, 1989.
J. W. L. Glaisher, On the residue of a binomial-theorem coefficient with respect to a prime modulus, Quart. J. Pure Appl. Math. 30 (1899), 150–156.
R. Graham, A. Yao, and F. Yao, Addition chains with multiplicative cost, Disc. Math. 23 (1978), 115–119.
J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multidimensional integrals, Numer. Math. 2 (1960), 84–90.
S. Lang, Algebra, Addison-Wesley, 1971.
D. H. Lehmer, K. Mahler, and A. J. van der Poorten, Integers with digits 0 or 1, Math. Comp. 46 (1986) 683–689.
J. H. Loxton and A. J. van der Poorten, An awful problem about integers in base four, Acta Arithmetica 49 (1987), 193–203.
A. de Luca and S. Varricchio, Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups, Theor. Comput. Sci. 63 (1989), 333–348.
M. Mendès France and A. J. van der Poorten, From geometry to Euler identities, Theor. Comput. Sci. 65 (1989), 213–220.
M. Mendès France and J. Shallit, Wire bending, J. Combinatorial Theory, A 50 (1989), 1–23.
P. Morton and W. Mourant, Paper folding, digit patterns, and groups of arithmetic fractals, Proc. Lond. Math. Soc. 59 (1989), 253–293.
L. Moser, An application of generating series, Math. Mag. 35 (1962), 37–38.
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc. 21 (1969), 719–721.
D. J. Newman and M. Slater, Binary digit distribution over naturally defined sequences, Trans. Amer. Math. Soc. 213 (1975), 71–78.
G. de Rham, Un peu de mathématiques à propos d'une courbe plane, Elem. Math. 2 (1947), 73–77; 89–97.
G. Rauzy, Suites à termes dans un alphabet fini, Sém. Théorie des Nombres de Bordeaux, 1982–3, 25.01–25.16.
B. Reznick, A new sequence with many properties, Abs. Amer. Math. Soc. 5 (1984), 16.
B. Reznick, Some extremal problems for continued fractions, Ill. J. Math. 29 (1985), 261–279.
O. Salon, Quelles tuiles! (Pavages apériodiques du plan et automates bidimensionnels), Séminaire de Théorie des Nombres de Bordeaux, (2ème Série) 1 (1989), 1–25.
M. P. Schützenberger, On the definition of a family of automata, Information and Control 4 (1961), 245–270.
N. J. A. Sloane, A handbook of integer sequences, Academic Press, 1973.
A. Salomaa and M. Soittola, Automata-theoretic aspects of formal power series, Springer-Verlag, 1978.
M. A. Stern, Über eine zahlentheoretische Funktion, J. reine angew. Math. 55 (1858), 193–220.
T. Tapsoba, Thèse de troisième cycle, Université d'Aix-Marseille II, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Allouche, JP., Shallit, J. (1990). The ring of k-regular sequences. In: Choffrut, C., Lengauer, T. (eds) STACS 90. STACS 1990. Lecture Notes in Computer Science, vol 415. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52282-4_28
Download citation
DOI: https://doi.org/10.1007/3-540-52282-4_28
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52282-9
Online ISBN: 978-3-540-46945-2
eBook Packages: Springer Book Archive