Two-dimensional cellular automata and deterministic on-line tessalation automata
In this work we consider the relationships between the classes of two-dimensional languages defined by deterministic on-line tessellation automata and by real time two-dimensional cellular automata with Moore and Von Neumann neighborhood. We generalize the result known for one-dimensional cellular automata to two-dimensional cellular automata with Von Neumann neighborhood: the class of real time cellular automata is closed under rotation of 180degrees if and only if real time cellular automata is equivalent to linear time cellular automata. (C) 2002 Elsevier Science B.V. All rights reserved.
cellular automata deterministic on-line tessalation automata real time linear time closure property