Stupeň expanze slov lexikalizovaného RRWW-automatu: nová míra nedeterminismu (bezkontextových) jazyků.
Abstrakt
Restartovací automaty mohou být považovány za analytickou variantu klasických automatů i za regulované přepisovací systémy. Studujeme míru nedeterminismu jazyků v termínech (silně) lexikalizovaných deterministických restartovacích automatů.
Tato míra je založena na počtu pomocných symbolů ve slově potřebných pro rozpoznání jazyka jako projekce charakteristického jazyka na vstupní abecedu. Tento způsob rozpoznávání je typický pro redukční analýzu, metodu sloužící v lingvistice na vytváření a verifikaci formálního popisu přirozeného jazyka.
Hlavním výsledkem jsou hierarchie tříd bezkontextových jazyků a dvě hierarchie tříd kontextových jazyků, které jsou založeny na stupni expanze jazyka.