Simulations Between Cellular Automata on Trees Extended by Horizontal Edges

Issue title: Cellular Automata

Article type: Research Article

Authors: Worsch, Thomas

Affiliations: Fakultät für Informatik, Universität Karlsruhe, Germany

Abstract: In this paper we consider cellular automata where the graph defined by the neighbourhood relations between the cells is a tree “with additional edges”. This includes hyperbolic CA defined by regular tessellations of the two-dimensional hyperbolic plane. It is shown that all X-tree CA and all hyperbolic CA can C-simulate each other with constant slowdown, independent of the “branching factors” of the underlying trees.

Keywords: cellular automata, extended tree, X-tree, hyperbolic CA

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 241-260, 2003