Show simple item record

dc.date.accessioned2008-10-06T07:23:43Z
dc.date.available2008-10-06T07:23:43Z
dc.date.issued2008-10-06T07:23:43Z
dc.identifier.uriurn:nbn:de:hebis:34-2008100624308
dc.identifier.urihttp://hdl.handle.net/123456789/2008100624308
dc.format.extent227942 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.subjectrestarting automatoneng
dc.subjectCD-system of restarting automataeng
dc.subjectlanguage classeng
dc.subjecthierarchyeng
dc.subjectlower bound techniqueeng
dc.subject.ddc004
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 Informatikschriftenger
dcterms.isPartOf2008, 2ger
dc.subject.ccsF.1.1
dc.subject.ccsF.4.3


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record