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

Please use this identifier to cite or link to this item: http://nbn-resolving.de/urn:nbn:de:hebis:34-200604059045

Title: Shrinking restarting automata
Authors: Jurdzinski, TomaszOtto, Friedrich
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 2005
Publisher: Universität Kassel, FB 17, Mathematik/Informatik
Series/Report no.: Mathematische Schriften Kassel05, 01
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.
URI: urn:nbn:de:hebis:34-200604059045
Appears in Collections:Mathematische Schriften Kassel

Files in This Item:

File Description SizeFormat
MSK05_01.pdf297.3 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.