Detail publikace

Rewriting Systems with Restricted Configurations

KŘIVKA Zbyněk. Rewriting Systems with Restricted Configurations. Brno: Fakulta informačních technologií VUT v Brně, 2008. ISBN 978-80-214-3722-7.
Název česky
Přepisující systémy s omezenými konfiguracemi
Typ
kniha
Jazyk
angličtina
Autoři
Abstrakt

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.

Rok
2008
Strany
131
ISBN
978-80-214-3722-7
Vydavatel
Fakulta informačních technologií VUT v Brně
Místo
Brno, CZ
BibTeX
@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"
}
Soubory
Nahoru