Automaticity of Rational Functions

Abstract: We study double sequences with values in a finite commutative ring $\cal R$. We discuss under which conditions a double sequence, which is given by a rational function, is definable in $\langle\hbox N,+\rangle$. Moreover, we give a complete characterization of the automaticity properties og double sequences defined by rational functions with coefficients in the ring $\hbox Z/(m)=\hbox Z/m\hbox Z$. Thus answering a question posed by Salon in Suites automatiques arithmetiques des automates multidimensionales, Theses, Universite Bordeaux I, (1989), p. II-9.

Keywords: finite commutative ring; automaticity properties; double sequence

Classification (MSC91): 13M05 classification2:

Full text of the article:

• Compressed DVI file (18639 Bytes)
• Compressed Postscript file (76796 Bytes)