Disertace

 
Křivka, Z.: Přepisující systémy s omezenými konfiguracemi, Brno, CZ, 2007, s. 98
Jazyk publikace:čeština
Název publikace:Přepisující systémy s omezenými konfiguracemi
Název (en):Rewriting Systems with Restricted Configurations
Strany:98
Místo vydání:Brno, CZ
Rok:2007
Soubory: 
+Typ Jméno Název Vel. Změněn
iconkrivka_dp_2007-10-09.pdf1,03 MB2007-10-09 18:36:29
^ Vybrat vše
S vybranými:
Klíčová slova
\#-přepisující systém, determinismus, dynamická složitost, formální model, jazyk, konečný index, konfigurace, $n$-limitovanost, $m$-paralelní $n$-pravě-lineární jednoduchá maticová gramatika, omezování, popisná složitost, programovaná gramatika, redukující hluboký zá\-so\-bní\-ko\-vý automat, stavová gramatika, řízený přepisující systém, vyjadřovací schopnost, třída jazyků, zásobníkový automat s~omezeným obsahem zásobníku
Anotace
Tato teoretická dizertační práce zastřešuje pod pojmem přepisující systémy formální 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 systémů 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 systémů s~důrazem na omezování konfigurací a posloupností aplikovaných pravidel. Práce též představuje pojem dy\-na\-mi\-cká složitost, který se zaměřuje na omezování vybraných me\-trik 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í).
  V~zá\-vi\-slo\-sti 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 existu\-jí\-cích kombinovaných, omezovaných a řízených přepisujících systémů.
Hlavním vý\-sled\-kem jsou nekonečné hie\-rar\-chie 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.
BibTeX:
@PHDTHESIS{
   author = {Zbyněk Křivka},
   title = {Přepisující systémy s omezenými konfiguracemi},
   pages = {98},
   year = {2007},
   location = {Brno, CZ},
   language = {czech},
   url = {http://www.fit.vutbr.cz/research/view_pub.php?id=8479}
}