Contribution in edited book
On the gapcomplexity of simple RLautomata
Publication Details
Authors:  Mraz, F.; Otto, F.; Platek, M.

Editor:  Oscar H., Ibarra; Zhe, Dang

Book title:  Developments in Language Theory, DLT 2006, Proc.

Title of series:  Lecture Notes in Computer Science 4036

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 socalled tsRLautomaton, which is an RLautomaton 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 gapcomplexity of these automata. The membership problem for a language that is accepted by a tsRLautomaton with a bounded number of gaps can be solved in polynomial time. On the other hand, tsRLautomata with an unbounded number of gaps accept NPcomplete languages.