Technischer Report
Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata
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.
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.
Citation
@techreport{urn:nbn:de:hebis:34-2008100624308,
author={Otto, Friedrich},
title={Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata},
year={2008}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2008$n2008 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2008100624308 3000 Otto, Friedrich 4000 Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata / Otto, Friedrich 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2008100624308=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2008, 2 7136 ##0##urn:nbn:de:hebis:34-2008100624308
2008-10-06T07:23:43Z 2008-10-06T07:23:43Z 2008-10-06T07:23:43Z urn:nbn:de:hebis:34-2008100624308 http://hdl.handle.net/123456789/2008100624308 227942 bytes application/pdf eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ restarting automaton CD-system of restarting automata language class hierarchy lower bound technique 004 Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata Technischer Report 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. open access Otto, Friedrich Kasseler Informatikschriften ;; 2008, 2 F.1.1 F.4.3 Kasseler Informatikschriften 2008, 2
The following license files are associated with this item:
:Urheberrechtlich geschützt