Abstrakt
Redukční analýza je metodou používanou v lingvistice pro kontrolu správnosti vět přirozených jazyků. Tato metoda je modelována pomocí restartovacích automatů.
Zde se zavádí a studuje nový typ restartovacích automatů, tak zvaný t-sRL-automat, jenž je RL-automatem s pracovním oknem velikosti 1, a který splňuje podmínku minimální acceptance. Na druhé straně, může provádět až vypouštěcích kroků v cyklu.
Zde studujeme tzv. gap-complexity těchto automatů. Membership problém pro jazyky přijímané pomocí t-sRL-automatů s omezeným počtem děr (gaps) je řešitelný v polynomiálním čase.
Na druhé straně, t-sRL-automaty neomezeým počtem děr přijímají NP-úplné jazyky.