Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Iterative arrays with a wee bit alternation

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


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


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


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 ; 9905 / 1999
Sprache: Englisch
Erstellungsjahr: 1999
Publikationsdatum: 18.08.1999
Kurzfassung auf Englisch: An iterative array is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. We are investigating iterative arrays with an alternating communication cell. All the other automata are deterministic. The number of alternating state transitions is regarded as a limited resource which depends on the length of the input.


We center our attention to real­time computations and compare alternating IAs with nondeterministic IAs. By proving that the language families of the latter are not closed under complement for sublogarithmic limits it is shown that alternation is strictly more powerful than nondeterminism. Moreover, for these limits there exist infinite hierarchies of properly included alternating language families. It is shown that these families are closed under boolean operations.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand