Anzeige
Erschienen in:
2000 | OriginalPaper | Buchkapitel
Linear Time Language Recognition on Cellular Automata with Restricted Communication
verfasst von : Thomas Worsch
Erschienen in: LATIN 2000: Theoretical Informatics
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
It is well-known that for classical one-dimensional one-way CA (OCA) it is possible to speed up language recognition times from (1 + r)n, r ∈ R + , to (1 + r/2)n. In this paper we show that this no longer holds for OCA in which a cell can comminucate only one bit (or more generally a fixed amount) of information to its neighbor in each step. For arbitrary real numbers r2 > r1 > 1 in time r2n 1-bit OCA can recognize strictly more languages than those operating in time r1n. Thus recognition times may increase by an arbitrarily large constant factor when restricting the communication to 1 bit. For two-way CA there is also an infinite hierarchy but it is not known whether it is as dense as for OCA. Furthermore it is shown that for communication restricted CA two-way flow of information can be much more powerful than an arbitrary number of additional communication bits.