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
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).
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
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).
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
Dokumenty
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"
}