Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://geb.uni-giessen.de/geb/volltexte/1998/18/


On time computability of functions in one-way cellular automata

Buchholz, Thomas ; Kutrib, Martin


pdf-Format: Dokument 1.pdf (293 KB)
ps gepackt: class="frontdoor">Dokument1.gz (198 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Arbeitsgruppe Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: Bericht / Arbeitsgruppe Informatik ; 9502 / 1995
Sprache: Englisch
Erstellungsjahr: 1995
Publikationsdatum: 26.05.1998
Kurzfassung auf Englisch: The capability of one­way (space­bounded) cellular automata (OCA) to time­compute functions is investigated. That means given an constant input of length n a distinguished cell has to enter a distinguished state exactly after f(n) time steps. The family of such functions (C (OCA)) is characterized in terms of formal language recognition. Several functions are proved to be time­computable and properties of C(OCA) are given. The time­computation at some points is concerned with the concept of signals and their realization which is quite formally defined for the first time.