<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
A Semigroup Approach to Automaticity
Andreas W.M. Dress1 and F.von Haeseler2
1Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, 33501, Bielefeld, Germany
2ESAT/SISTA KU-Leuven, Kasteelpark Arenberg 10, 3001 Leuven, Belgium
Annals of Combinatorics 7 (2) p.171-190 June, 2003
AMS Subject Classification: 11B85, 68Q45, 16W22, 18DXX
We present an abstract, yet rather natural concept of automaticity which is based on semigroup actions. The standard notion of k-automaticity as well as many, if not all of its generalizations are recovered by specifying appropriate semigroup actions on or or other similar objects --- e.g., the standard notion of k-automaticity is recovered by considering a certain ``natural'' action of the free semigroup with k generators on . We show that the main results characterizing automatic sequences (Cobham, 1972, Math. Systems Theory 6) hold almost verbatim in the general context, too.
Keywords: automatic sequences, finite automata, semigroup actions, categories


1. J.-P. Allouche, Automates finis en théorie des nombres, Exposition. Math. 5 (1987) 239–266.

2. J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992) 163–197.

3. J.-P. Allouche and M. Mendès France, Automata and automatic sequences, In: Beyond Quasicristals, F. Axel et al. Eds., Les Editions de Physique, Springer, Berlin, 1994, pp. 293–367.

4. J.-P. Allouche, E. Cateland, W.J. Gilbert, H.-O. Peitgen, J.O. Shallit, and G. Skordev, Automatic maps in exotic numeration systems, Theory Comput. Syst. 30 (1997) 285–331.

5. P.-G. Becker, k-regular power series and Mahler-type functional equations, J. Number Theory 49 (1994) 269–286.

6. J.R. Brown jr, Zeckendorf's theorem and some applications, Fibonacci Quart. 2 (1964) 162– 168.

7. V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 191–238.

8. V. Bruyère, G. Hansel, C. Michaux, and R. Villemaire, Correction to: logic and precognizable sets of integers, Bull. Belg. Math. Soc. 1 (1994) 577.

9. G. Christol, Ensembles presque périodiques k-reconnaissables, Theoret. Comput. Sci. 9 (1979) 141–145.

10. 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.

11. A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory 3 (1969) 186–192.

12. A. Cobham, Uniform tag sequences, Math. Systems Theory 6 (1972) 164–192.

13. P. Dumas, Algebraic aspects of B-regular sequences, In: Automata, Languages and Programming, Lecture Notes in Computer Science, A. Lingas, R. Karlsson, and S. Carlsson Eds., Springer-Verlag, 1993, pp. 457–468.

14. S. Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1985.

15. F. von Haeseler, Automatic Sequences, Walter de Gruyter, Berlin, 2003.

16. F. von Haeseler and W. Jürgensen, Automaticity of solutions of Mahler equations, In: Sequences and Their Applications, C. Ding, T. Helleseth, and H. Niedereiter Eds., Springer- Verlag, London, 1999, pp. 228–239.

17. W. Jürgensen, Equation kernels as a link between automaticity and Mahler equations, Ph.D. Thesis, Universität Bremen, 2000.

18. I. Kátai and J. Szabo, Canonical number systems for complex integers, Acta Sci. Math. (Szeged) 37 (1975) 255–280.

19. D. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd Ed., Addison Wesley, Mass., 1988.

20. A.J. van der Poorten, Substitution automata, functional equations and functions algebraic over a finite field, Contemp. Math. 9 (1982) 307–312.

21. S. Lang, Algebra, Addison-Wesley, 1977.

22. B. Randé, Équations fonctionelles des Mahler et fonctions élémentaires, Thèse, Univeristé de Bordeaux, 1992.

23. O. Salon, Suites automatiques á multi-indices, Séminaire de Théorie des nombres Bordeaux, Exp. 4 (1986/1987) 4-01–4-27.

24. O. Salon, Suites automatiques á multi-indices et algébricité, C. R. Acad. Sci. Paris, Sér. I Math. 305 (1987) 501–504.

25. J. Shallit, A generalization of automatic sequences, Theoret. Comput. Sci. 61 (1988) 1–16.

26. E. Zeckendorf, A generalized Fibonacci numeration, Fibonacci Quart. 10 (1972) 365–372.