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/22/


On the power of one-way bounded cellular time computers

Buchholz, Thomas ; Kutrib, Martin


pdf-Format: Dokument 1.pdf (203 KB)
ps gepackt: class="frontdoor">Dokument1.gz (133 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 ; 9604 / 1996
Sprache: Englisch
Erstellungsjahr: 1996
Publikationsdatum: 23.06.1998
Kurzfassung auf Englisch: Comparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to time­construct and time­compute functions. Time­construction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas time­computation requires the distinguished cell to enter a distinguished state firstly at time step f(n), where n is the length of the input. Here the family of functions which are time­constructible by a two­way unbounded cellular space (F(CS)) is characterized in terms of functions which are time­computable by one of the simplest cellular devices, a one­way bounded cellular automaton (C (OCA)). Conceptually, time­constructible functions have to be strictly increasing. Regarding that restriction the reverse characterization is shown, too. Some results concerning the structure of F(CS) and C(OCA) and their relation to formal language recognition are established.