Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436941 | Theoretical Computer Science | 2006 | 15 Pages |
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