2007 | OriginalPaper | Buchkapitel
Real Time Language Recognition on 2D Cellular Automata: Dealing with Non-convex Neighborhoods
verfasst von : Martin Delacourt, Victor Poupet
Erschienen in: Mathematical Foundations of Computer Science 2007
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.