Résumé
In this paper we study language recognition by two-dimensional cellular automata on different possible neighborhoods. Since it is known that all complete neighborhoods are linearly equivalent we focus on a natural sub-linear complexity class: the real time.
We show that any complete neighborhood is sufficient to recognize in real time any language that can be recognized in real-time by a cellular automaton working on the convex hull of V.