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

Rewriting Systems with Restricted Configurations

dizertace

čeština

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.

This theoretically oriented dissertation discusses rewriting systems, including various automata and grammars.  It concentrates its attention upon their combination.  More specifically, the central role of the present dissertation plays the general notion of a configuration as an instantaneous description of a rewriting system.  Based upon various restrictions placed upon configurations and rewriting modes, the systems are classified and studied. Apart from this major topic, the dissertation also discusses dynamic complexity, which is based upon metrics placed upon the process of yielding strings.\          As its fundamental topic, the dissertation discusses \#-rewriting system,  reducing deep pushdown automaton, and pushdown automata with restricted pushdowns. In addition, it studies some variants of \#-rewriting systems, including $n$-right linear and generalized \#-rewriting system.  In general, the dissertation demonstrates how the generative power of the systems under discussion depends upon the restrictions placed upon them. In terms of dynamic complexity, it discusses a close relationship between various rewriting systems, including newly introduced systems.  As its main result, the dissertation demonstrates several infinite hierarchies of language families defined by rewriting systems in dependency on their restrictions.        The conclusion demonstrates the application-important properties of the systems discussed in the dissertation. It sketches two new types of determinism and canonical rewriting; then, it demonstrates their potential practical usage.

\#-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

\#-rewriting system, configuration, descriptional complexity, determinism, dynamic complexity, finite index, formal model, generative power, language, language family, $n$-limitation, $m$-parallel $n$-right-linear simple matrix grammar, programmed grammar, pushdown automaton with restricted pushdown content, reducing deep pushdown automaton, regulated rewriting system, restriction, state grammar

KŘIVKA, Z.

4. 10. 2007

Brno

98

https://www.fit.vut.cz/research/publication/8479/

krivka_dp_2007-10-09.pdf