DSpace
KOBRA
KOBRA

KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 16 Elektrotechnik / Informatik  → Kasseler Informatikschriften (KIS)  

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://nbn-resolving.de/urn:nbn:de:hebis:34-2008100624308

Titel: Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata
Autor(en): Otto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 6-Okt-2008
Serie/Report Nr.: Kasseler Informatikschriften2008, 2
Zusammenfassung: The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.
URI: urn:nbn:de:hebis:34-2008100624308
Sammlung(en):Kasseler Informatikschriften (KIS)

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
Technicalreport2008_2.pdf234,55 kBAdobe PDFÖffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.