Detail publikace
Rewriting Systems with Restricted Configurations
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.
@BOOK{FITPUB8768,
author = "Zbyn\v{e}k K\v{r}ivka",
title = "Rewriting Systems with Restricted Configurations",
pages = 131,
year = 2008,
location = "Brno, CZ",
publisher = "Faculty of Information Technology BUT",
ISBN = "978-80-214-3722-7",
language = "english",
url = "https://www.fit.vut.cz/research/publication/8768"
}