| 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: | |
|---|
|
| | 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}
} |
|