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
