Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

On interacting automata with limited nondeterminism

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


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


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


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 ; 9806 / 1998
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 18.08.1999
Kurzfassung auf Englisch: One­way and two­way cellular language acceptors with restricted non­ determinism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real­time, linear­time and unrestricted­time computations. A speed­up result that allows any linear­time computation to be sped­up to real­time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and [Epsilon]­free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand