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 se studuje zachovávání správnosti těmito automaty na jedné straně a složitost těchto automatů na druhé straně. Je zavedena a studována popisná složitost t-sRL-automatů v termínech tzv. meta-instrukcí.
Prezentujeme jako výsledek složitostní hierarchii a ukazujeme, že correctness preserving nedeterministické t-sRL-automaty nejsou z hlediska rozpoznávání silnější než deterministické t-sRL-automaty.