"On the Gap-Complexity of Simple RL-Automata" . "[FB020F99D7FE]" . . . "On the Gap-Complexity of Simple RL-Automata" . "3"^^ . "CZ - \u010Cesk\u00E1 republika" . . . "2"^^ . "4036/2006" . "0302-9743" . "O d\u011Brov\u00E9-slo\u017Eitosti jednoduch\u00FDch RL- automat\u016F"@cs . "RIV/00216208:11320/06:00002821" . . "O d\u011Brov\u00E9-slo\u017Eitosti jednoduch\u00FDch RL- automat\u016F"@cs . . . "Reduk\u010Dn\u00ED anal\u00FDza je metodou pou\u017E\u00EDvanou v lingvistice pro kontrolu spr\u00E1vnosti v\u011Bt p\u0159irozen\u00FDch jazyk\u016F. Tato metoda je modelov\u00E1na pomoc\u00ED restartovac\u00EDch automat\u016F. Zde se zav\u00E1d\u00ED a studuje nov\u00FD typ restartovac\u00EDch automat\u016F, tak zvan\u00FD t-sRL-automat, jen\u017E je RL-automatem s pracovn\u00EDm oknem velikosti 1, a kter\u00FD spl\u0148uje podm\u00EDnku minim\u00E1ln\u00ED acceptance. Na druh\u00E9 stran\u011B, m\u016F\u017Ee prov\u00E1d\u011Bt a\u017E vypou\u0161t\u011Bc\u00EDch krok\u016F v cyklu. Zde studujeme tzv. gap-complexity t\u011Bchto automat\u016F. Membership probl\u00E9m pro jazyky p\u0159ij\u00EDman\u00E9 pomoc\u00ED t-sRL-automat\u016F s omezen\u00FDm po\u010Dtem d\u011Br (gaps) je \u0159e\u0161iteln\u00FD v polynomi\u00E1ln\u00EDm \u010Dase. Na druh\u00E9 stran\u011B, t-sRL-automaty neomeze\u00FDm po\u010Dtem d\u011Br p\u0159ij\u00EDmaj\u00ED NP-\u00FApln\u00E9 jazyky."@cs . "On the Gap-Complexity of Simple RL-Automata"@en . . . "83;94" . "Lecture Notes In Computer Science" . "12"^^ . "4036" . . "On the Gap-Complexity of Simple RL-Automata"@en . "Gap-Complexity; Simple; RL-Automata"@en . "RIV/00216208:11320/06:00002821!RIV07-GA0-11320___" . . "Mr\u00E1z, Franti\u0161ek" . . . "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 . "Pl\u00E1tek, Martin" . . "11320" . "P(1ET100300517), P(GA201/04/2102), Z(MSM0021620838)" . . . "490458" . "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." . . . .