DSpace
KOBRA
KOBRA

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:
http://nbn-resolving.de/urn:nbn:de:hebis:34-2006110215424

Titel: On the Descriptional Complexity of Simple RL-Automata
Autor(en): Messerschmidt, HartmutMráz, FrantišekOtto, FriedrichPlátek, Martin
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 2006
Serie/Report Nr.: Mathematische Schriften Kassel06, 04
Zusammenfassung: 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
Sammlung(en):Mathematische Schriften Kassel

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
prep0604.pdf216,75 kBAdobe PDFÖffnen/Anzeigen

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons
Creative Commons

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.