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

Titel: On the Gap-Complexity of Simple RL-Automata
Autor(en): Mráz, FrantišekOtto, FriedrichPlátek, Martin
Klassifikation (DDC): 004 - Informatik (Data processing Computer science)
Erscheinungsdatum: 2006
Serie/Report Nr.: Mathematische Schriften Kassel06, 02
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. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one 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. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.
URI: urn:nbn:de:hebis:34-2006053112600
Sammlung(en):Mathematische Schriften Kassel

Dateien zu dieser Ressource:

Datei Beschreibung GrößeFormat
prep0602.pdf207,91 kBAdobe PDFÖffnen/Anzeigen

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.