zbMATH — the first resource for mathematics

Automaticity of rational functions. (English) Zbl 0895.68093
Summary: We study double sequences with values in a finite commutative ring \({\mathcal R}\). We discuss under which conditions a double sequence, which is given by a rational function, is definable in \(\langle \mathbb{N},+ \rangle\). Moreover, we give a complete characterization of the automaticity properties of double sequences defined by rational functions with coefficients in the ring \(\mathbb{Z}/(m)= \mathbb{Z}/m \mathbb{Z}\). Thus answering a question posed by O. Salon in: Propriétés arithmétiques des automates multidimensionneles [Thèse, Université Bordeaux I (1989), p. II–9].

68Q80 Cellular automata (computational aspects)
11B85 Automata sequences
68Q45 Formal languages and automata
13M05 Structure of finite commutative rings
68R15 Combinatorics on words
PDF BibTeX Cite
Full Text: EMIS EuDML