Technischer Report
CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions
Abstract
We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton.
Citation
@techreport{urn:nbn:de:hebis:34-2009121031420,
author={Otto, Friedrich},
title={CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions},
year={2009}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2009$n2009 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-2009121031420 3000 Otto, Friedrich 4000 CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions / Otto, Friedrich 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-2009121031420=x R 4204 \$dTechnischer Report 4170 Kasseler Informatikschriften ;; 2009, 2 7136 ##0##urn:nbn:de:hebis:34-2009121031420
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2009-12-10T14:31:08Z 2009-12-10T14:31:08Z 2009-12-10T14:31:08Z urn:nbn:de:hebis:34-2009121031420 http://hdl.handle.net/123456789/2009121031420 eng Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Restarting automaton CD-system modes of operation 004 CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions Technischer Report We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton. open access Otto, Friedrich Kasseler Informatikschriften ;; 2009, 2 F.1.1 F.4.3 Kasseler Informatikschriften 2009, 2 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt