Cellular Automata on a G-Set
Sebastien Moriceau
In this paper, we extend the usual definition of cellular automaton on a group in order to deal with a new kind of cellular automata, like cellular automata in the hyperbolic plane and we explore some properties of these cellular automata. This definition also allows to deal with maps, intuitively considered as cellular automata, even if they did not match the usual definition, like the Margolus billiard-ball. One of the main results is an extension of Hedlund’s theorem for these cellular automata.
Keywords: cellular automaton, G-set, hyperbolic space, Hedlund’s theorem, reversible cellular automaton, coordinate system, group action.