×

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)].

MSC:

11B85 Automata sequences
11A63 Radix representation; digital problems
16Y60 Semirings
68Q45 Formal languages and automata
68R05 Combinatorics in computer science

Citations:

Zbl 0870.68105
Full Text: DOI