Rewriting Systems with Restricted Configurations

#-rewriting system, configuration, descriptional complexity, determinism, dynamic complexity, finite index, formal model, generative power, language, language family, n-limitation, m-parallel n-right-linear simple matrix grammar, programmed grammar, restricted pushdown automaton, reducing deep pushdown automaton, regulated rewriting system, restriction, state grammar

Tato teoreticka dizertační práce zastřešuje pod pojmem přepisující systémy formalní modely gramatik a automatů a zkoumá možnosti jejich kombinování. Zobecňuje pojem konfigurace pro označení vnitřního stavu přepisujících systemů a sjednocuje i některé další pojmy z oblasti gramatik a automatů. Dále klasifikuje různé přístupy k omezování přepisujících systemů s důrazem na omezování konfigurací a posloupnosti aplikovaných pravidel. Práce též představuje pojem dynamická složitost, který se zaměřuje na omezování vybraných metrik při procesu zpracovávání věty přepisujícím systémem.    Hlavní část práce představuje dva nové kombinované modely (#-přepisující systémy a redukující hluboké zásobníkové automaty) a jeden omezovaný systém (zásobníkové automaty s omezeným obsahem zásobníku). V případě #-přepisujících systémů bylo navíc detailněji studováno několik modifikací (n-pravě-lineární a zobecněné \#-přepisující systémy inspirované Chomského hierarchií jazyků). V závislosti na způsobu omezování prezentuje text výsledky ohledně vyjadřovacích schopností těchto formálních modelů. Demonstruje také úzký vztah nových i vybraných existujících kombinovaných, omezovaných a řízených přepisujících systémů. Hlavním výsledkem jsou nekonečné hierarchie tříd jazyků definované těmito přepisujícími systémy podle parametrů omezování (konečný index, n-limitovanost, hloubka).    V závěru jsou studovány vlastnosti těchto systémů s úzkou vazbou na praxi. Text zavádí dva z možných způsobů definice determinismu a kanoničnosti #-přepisujících systémů a demonstruje jejich vztah k potencionální praktické využitelnosti.