Detail publikace

Přepisující systémy s omezenými konfiguracemi

KŘIVKA, Z.

Originální název

Přepisující systémy s omezenými konfiguracemi

Český název

Přepisující systémy s omezenými konfiguracemi

Typ

dizertace

Jazyk

cs

Originální abstrakt

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.

Český abstrakt

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.

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

Vydáno

04.10.2007

Místo

Brno

Strany počet

98

BibTex 


@phdthesis{BUT66829,
  author="Zbyněk {Křivka}",
  title="Přepisující systémy s omezenými konfiguracemi",
  annote="
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.
",
  chapter="66829",
  year="2007",
  month="october",
  type="dissertation"
}