Register Cellular Automata in the Hyperbolic Plane

Article type: Research Article

Authors: Grigorieff, Serge | Margenstern, Maurice

Affiliations: LIAFA, Université Paris 7, 2, pl. Jussieu 75251 Paris Cedex 05, France | LITA, EA 3097, Université de Metz, Île du Saulcy 57045 Metz Cedex, France

Abstract: In this paper, we consider cellular automata on special grids of the hyperbolic plane: the grids are constructed on infinigons, i.e. polygons with infinitely many sides. We show that the truth of arithmetical formulas can be decided in finite time with infinite initial recursive configurations. Next, we define a new kind of cellular automata, endowed with data and more powerful operations which we call register cellular automata. This time, starting from finite configurations, it is possible to decide the truth of arithmetic formulas in linear time with respect to the size of the formula.

Journal: Fundamenta Informaticae, vol. 61, no. 1, pp. 19-27, 2004