Register Cellular Automata in the Hyperbolic Plane

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.