Preprint
Shrinking restarting automata
Abstract
Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.
Citation
@article{urn:nbn:de:hebis:34-200604059045,
author={Jurdzinski, Tomasz and Otto, Friedrich},
title={Shrinking restarting automata},
year={2005}
}
0500 Oax 0501 Text $btxt$2rdacontent 0502 Computermedien $bc$2rdacarrier 1100 2005$n2005 1500 1/eng 2050 ##0##urn:nbn:de:hebis:34-200604059045 3000 Jurdzinski, Tomasz 3010 Otto, Friedrich 4000 Shrinking restarting automata / Jurdzinski, Tomasz 4030 4060 Online-Ressource 4085 ##0##=u http://nbn-resolving.de/urn:nbn:de:hebis:34-200604059045=x R 4204 \$dPreprint 4170 Mathematische Schriften Kassel 7136 ##0##urn:nbn:de:hebis:34-200604059045
<resource xsi:schemaLocation="http://datacite.org/schema/kernel-2.2 http://schema.datacite.org/meta/kernel-2.2/metadata.xsd"> 2006-04-05T12:48:59Z 2006-04-05T12:48:59Z 2005 urn:nbn:de:hebis:34-200604059045 http://hdl.handle.net/123456789/200604059045 304431 bytes application/pdf eng Universität Kassel, FB 17, Mathematik/Informatik Urheberrechtlich geschützt https://rightsstatements.org/page/InC/1.0/ Theoretische Informatik Reduktionssystem 004 Shrinking restarting automata Preprint Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes. open access Jurdzinski, Tomasz Otto, Friedrich Mathematische Schriften Kassel 05, 01 Mathematische Schriften Kassel 05, 01 </resource>
The following license files are associated with this item:
:Urheberrechtlich geschützt