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/
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:
08.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
