Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Differences Between 2D Neighborhoods According to Real Time Computation
verfasst von : Anael Grandjean
Erschienen in: Developments in Language Theory
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
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 \(\mathcal {N}\) and \(\mathcal {N}'\), if \(\mathcal {N}\) has a limiting vertex in some direction and \(\mathcal {N}'\) have no vertex in that direction then there is a language recognizable in real time with \(\mathcal {N}'\) and not with \(\mathcal {N}\). One easy corollary is that real time classes for two neighborhoods may be incomparable (and such neighborhoods are easy to construct).