Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata
| dc.date.accessioned | 2008-10-06T07:23:43Z | |
| dc.date.available | 2008-10-06T07:23:43Z | |
| dc.date.issued | 2008-10-06T07:23:43Z | |
| dc.format.extent | 227942 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | urn:nbn:de:hebis:34-2008100624308 | |
| dc.identifier.uri | http://hdl.handle.net/123456789/2008100624308 | |
| dc.language.iso | eng | |
| dc.rights | Urheberrechtlich geschützt | |
| dc.rights.uri | https://rightsstatements.org/page/InC/1.0/ | |
| dc.subject | restarting automaton | eng |
| dc.subject | CD-system of restarting automata | eng |
| dc.subject | language class | eng |
| dc.subject | hierarchy | eng |
| dc.subject | lower bound technique | eng |
| dc.subject.ccs | F.1.1 | |
| dc.subject.ccs | F.4.3 | |
| dc.subject.ddc | 004 | |
| dc.title | Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata | eng |
| dc.type | Technischer Report | |
| dcterms.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. | eng |
| dcterms.accessRights | open access | |
| dcterms.creator | Otto, Friedrich | |
| dcterms.isPartOf | Kasseler Informatikschriften ;; 2008, 2 | ger |
| dcterms.source.series | Kasseler Informatikschriften | ger |
| dcterms.source.volume | 2008, 2 | ger |