Tools for devising cellular automata in the hyperbolic 3D space

Issue title: Cellular Automata

Article type: Research Article

Authors: Margenstern, Maurice | Skordev, Gencho

Affiliations: LITA, EA 3097, Université de Metz, Île du Saulcy, 57045 Metz Cédex, France | CeVis, Fachbereich Mathematik, Universität Bremen, Universitätsallee, 29, 28359 Bremen, Germany

Abstract: The study of cellular automata (CA) on tilings of hyperbolic plane was initiated in [13]. Appropriate tools were developed which allow linear algorithms to implement cellular automata on the tiling of the hyperbolic plane with the regular rectangular pentagon. In this paper we tackle the problem of devising similar tools in the case of the 3D hyperbolic space. The tools are given for the rectangular dodecahedral tiling of the 3D hyperbolic space. We give an algorithm which computes all needed information from the number of a cell. The algorithm is cubic in time and quadratic in space.

Keywords: cellular automata, hyperbolic geometry, tilings, combinatorial geometry

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 369-398, 2003