Iterative arrays with a wee bit alternation

dc.contributor.authorBuchholz, Thomas
dc.contributor.authorKlein, Andreas
dc.contributor.authorKutrib, Martin
dc.date.accessioned2022-09-12T09:38:43Z
dc.date.available1999-08-18T22:00:00Z
dc.date.available2022-09-12T09:38:43Z
dc.date.issued1999
dc.description.abstractAn 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.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-1423
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7558
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6992
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 9905 / 1999
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleIterative arrays with a wee bit alternationen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id142
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
IfigReport9905.pdf
Größe:
251.67 KB
Format:
Adobe Portable Document Format