Article ID Journal Published Year Pages File Type
436941 Theoretical Computer Science 2006 15 Pages PDF
Abstract

In this paper, multidimensional cellular automaton are considered. We investigate the hierarchy designed by the low complexity classes when the dimensionality is increased. Whether this hierarchy is strict, is an open problem. However, we compare different variants and study their closure properties. We present also a correspondence between a main variant of multidimensional real-time cellular automata and one-way multihead alternating finite automata.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics