KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
§
Volltext
URN: urn:nbn:de:swb:90-AAA555993

Linear time language recognition on cellular automata with restricted communication

Worsch, Thomas

Abstract:
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, to (1+r/2)n (where r is any positive real number). 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 r_2>r_1>1 in time r_2*n 1-bit OCA can
recognize strictly more languages than those operating in time
r_1*n. Thus recognition times may increase by an arbitrarily
large constant factor when restricting the communication to 1
bit.


Zugehörige Institution(en) am KIT Lehrstuhl Informatik für Ingenieure und Naturwissenschaftler (Lehrstuhl Inf. für Ing. u. Naturwiss.)
Publikationstyp Forschungsbericht
Jahr 1999
Sprache Englisch
Identifikator ISSN: 1432-7864
KITopen ID: 55599
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 1998,25
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page