KIT | KIT-Bibliothek | Impressum | Datenschutz

Linear time language recognition on cellular automata with restricted communication

Worsch, Thomas


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

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