KOBRA - Dokumentenserver der Universität Kassel  → Fachbereiche  → FB 10 / Mathematik und Naturwissenschaften  → Institut für Mathematik  → Mathematische Schriften Kassel 

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:

Titel: Shrinking restarting automata
Autor(en): Jurdzinski, TomaszOtto, Friedrich
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 2005
Herausgeber: Universität Kassel, FB 17, Mathematik/Informatik
Serie/Report Nr.: Mathematische Schriften Kassel05, 01
Zusammenfassung: 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.
URI: urn:nbn:de:hebis:34-200604059045
Sammlung(en):Mathematische Schriften Kassel

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
MSK05_01.pdf297,3 kBAdobe PDFÖffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.