Automatic maps on a semiring with digits. (English) Zbl 0879.11010
This paper presents a generalization of the notion of automaticity for a sequence. (A sequence is said to be \(b\)-automatic if its \(n\)th term can be computed from the base \(b\)-expansion of \(n\) using a finite automaton with output.) More precisely, a notion of automaticity (and also of susbtitution of constant length) is given for maps from a semiring R (with radix representation) to a finite set: the integers are replaced by a numeration system consisting of the powers of a base \(b\) and an appropriate set of digits. This generalization contains the case of multidimensional automatic sequences and the case of sequences indexed by Gaussian integers, by rational integers or by quadratic irrationals. Note the impressive bibliography and the many illustrating examples of this paper. A more detailed version of this paper has appeared in [J.-P. Allouche, E. Cateland, W. J. Gilbert, H.-O. Peitgen, J. Shallit and G. Skordev, Theory Comput. Syst. 30, 285-331 (1997; Zbl 0870.68105)].
Reviewer: V.Berthé (Marseille)
MSC:
11B85 | Automata sequences |
11A63 | Radix representation; digital problems |
16Y60 | Semirings |
68Q45 | Formal languages and automata |
68R05 | Combinatorics in computer science |