Differences Between 2D Neighborhoods According to Real Time Computation
Abstract
Cellular automata are a parallel model of computation. This paper presents studies about the impact of the choice of the neighborhood on small complexity classes, mainly the real time class. The main result states that given two neighborhoods $N$ and $N’$, if $N$ has a limiting vertex in some direction and $N’$ have no vertex in that direction then there is a language recognizable in real time with $N’$ and not with $N$. One easy corollary is that real time classes for two neighborhoods may be incomparable (and such neighborhoods are easy to construct).