Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

One guess one-way cellular arrays

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


Zum Volltext im pdf-Format: Dokument 1.pdf (232 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-269
URL: http://geb.uni-giessen.de/geb/volltexte/1998/26/

Bookmark bei Connotea Bookmark bei del.icio.us


Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 9801 / 1998
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 09.07.1998
Kurzfassung auf Englisch: One­way cellular automata with restricted nondeterminism are investigated. The number of allowed nondeterministic state transitions is limited to a constant. It is shown that a limit to exactly one step does not decrease the language accepting capabilities. We prove a speed­up result that allows any linear­time computation to be sped­up to real­time. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the real­time languages.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand