CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions
Classification / Keywords
Collections
Rights
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.
@techreport{urn:nbn:de:hebis:34-2009121031420, author ={Otto, Friedrich}, title ={CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions}, copyright ={https://rightsstatements.org/page/InC/1.0/}, language ={en}, year ={2009-12-10T14:31:08Z} }