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

Title: On the Gap-Complexity of Simple RL-Automata
Authors: Mrá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, 02
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. 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
Appears in Collections:Mathematische Schriften Kassel

Files in This Item:

File Description SizeFormat
prep0602.pdf207.91 kBAdobe PDFView/Open

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