Beitrag in einem Sammelband
On the gap-complexity of simple RL-automata
Details zur Publikation
Autor(inn)en: | Mraz, F.; Otto, F.; Platek, M. |
Herausgeber: | Oscar H., Ibarra; Zhe, Dang |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2006 |
Seitenbereich: | 83-94 |
Buchtitel: | Developments in Language Theory, DLT 2006, Proc. |
Titel der Buchreihe: | Lecture Notes in Computer Science 4036 |
ISBN: | 978-3-540-35428-4 |
eISBN: | 978-3-540-35430-7 |
DOI-Link der Erstveröffentlichung: |
Zusammenfassung, 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 introduce and 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. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-sRL-automata with an unbounded number of gaps accept NP-complete languages.
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 introduce and 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. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-sRL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-sRL-automata with an unbounded number of gaps accept NP-complete languages.
Projekte
