. . "On the gap-complexity of simple RL-automata"@en . . . . . "[9A18C31DFFA5]" . . "Pl\u00E1tek, Martin" . "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."@en . "RIV/00216208:11320/06:00206167!RIV10-GA0-11320___" . . . . "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." . "On the gap-complexity of simple RL-automata" . "Mr\u00E1z, Franti\u0161ek" . "11320" . "000239454100009" . . "P(1ET100300517), P(GA201/04/2102), Z(MSM0021620838)" . "2"^^ . "12"^^ . "gap-complexity; simple; RL-automata"@en . . "On the gap-complexity of simple RL-automata"@en . "490457" . "3"^^ . "Berlin" . "Berlin" . "Developments in Language Theory" . "On the gap-complexity of simple RL-automata" . . . "978-3-540-35428-4" . . . . "2006-01-01+01:00"^^ . . "Springer-Verlag" . . . "Otto, Friedrich" . "RIV/00216208:11320/06:00206167" .