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/1999/139/


Iterative arrays with limited nondeterministic communication cell

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


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

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 (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: IFIG Research Report ; 9901 / 1999
Sprache: Englisch
Erstellungsjahr: 1999
Publikationsdatum: 01.03.1999
Kurzfassung auf Englisch: Iterative arrays with restricted nondeterminism are investigated. Non-determinism is provided for the distinguished communication cell only. All the other cells are deterministic ones. Moreover, the number of allowed nondeterministic state transitions is limited dependent on the length of the input. It is shown that the limit can be reduced by a constant factor without affecting the language accepting capabilities, but for sublogarithmic limits there exists a infinite hierarchy of properly included real­time language families. Finally we prove several closure properties of these families.