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

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-2008100624308

Title: Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata
Authors: Otto, Friedrich
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 6-Oct-2008
Series/Report no.: Kasseler Informatikschriften2008, 2
Abstract: 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
Appears in Collections:Kasseler Informatikschriften (KIS)

Files in This Item:

File Description SizeFormat
Technicalreport2008_2.pdf234.55 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.