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-2006110215424

Title: On the Descriptional Complexity of Simple RL-Automata
Authors: Messerschmidt, HartmutMráz, FrantišekOtto, FriedrichPlátek, Martin
???metadata.dc.subject.ddc???: 004 - Informatik (Data processing Computer science)
Issue Date: 2006
Series/Report no.: Mathematische Schriften Kassel06, 04
Abstract: Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.
URI: urn:nbn:de:hebis:34-2006110215424
Appears in Collections:Mathematische Schriften Kassel

Files in This Item:

File Description SizeFormat
prep0604.pdf216.75 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License
Creative Commons

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