Original title: Formální modely distribuovaného výpočtu
Translated title: Formal Models of Distributed Computation
Authors: Soukup, Ondřej ; Horváth,, Géza (referee) ; Rogalewicz, Adam (referee) ; Meduna, Alexandr (advisor)
Document type: Doctoral theses
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Tato disertační práce představuje derivační stromy několika různých typů gramatik ve zobecněné Kurodově normální formě; jmenovitě obecné a regulárně řízené gramatiky, gramatiky s rozptýleným kontextem a spolupracující distribuované gramatické systémy. Definuje jednoduché stromové rysy založené na kontextových vlastnostech jednotlivých diskutovaných gramatik a dokazuje, že pokud existuje limitující konstanta k taková, že každá věta generovaného jazyka L odpovídá řetězci listových uzlů derivačního stromu, ve kterém je výskyt definovaných stromových rysů omezen konstantou k, jazyk L je ve skutečnosti bezkontextový. Tato práce dále ukazuje, že dosažený výsledek představuje silný nástroj důkazu bezkontextovosti jazyka. Vše je doplněno příklady praktického využití nástroje. The present thesis introduces derivation trees for several different types of grammars in generalized Kuroda normal forms; namely, general, regular-controlled, and scattered context grammars and cooperating distributed grammar systems. It defines simple tree-based properties related to non-context-free properties of all grammars in question and shows that if there exists a limiting constant k such that every sentence in the generated language L is the frontier of a derivation tree in which the number of occurrences of the defined tree-based properties is limited by k, the language L is in fact context-free. The thesis explains that this result represents a powerful tool for showing languages to be context-free. It also provides illustrations and examples which sketch how to apply this tool in practice.
Keywords: bezkontextovost; bezkontextovost konečného indexu.; derivační stromy; gramatiky s rozptýleným kontextem; normalní formy; Obecné gramatiky; omezené derivační stromy; regulárně řízené bezkontextové gramatiky; spolupracující distribuované gramatické systémy; context-freeness; context-freeness of finite index.; cooperating distributed grammar systems; derivation trees; General grammars; normal forms; regular-controlled context-free grammars; restricted derivation trees; scattered context grammars

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/187311

Permalink: http://www.nusl.cz/ntk/nusl-412589


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Doctoral theses