Show simple item record
dc.format.extent227942 bytes
dc.rightsUrheberrechtlich geschützt
dc.subjectrestarting automatoneng
dc.subjectCD-system of restarting automataeng
dc.subjectlanguage classeng
dc.subjectlower bound techniqueeng
dc.titleLower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automataeng
dc.typeTechnischer Report
dcterms.abstractThe 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.accessRightsopen access
dcterms.creatorOtto, Friedrich
dcterms.isPartOfKasseler Informatikschriften ;; 2008, 2ger
dcterms.source.seriesKasseler Informatikschriftenger
dcterms.source.volume2008, 2ger

Files in this item


This item appears in the following Collection(s)

Show simple item record