|
|
Formal Models of Distributed Computation
Soukup, Ondřej ; Horváth,, Géza (referee) ; Rogalewicz, Adam (referee) ; Meduna, Alexandr (advisor)
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.
|
|
|
On Parallel Processing in Formal Models: Jumping Automata and Normal Forms
Kocman, Radim ; Černá, Ivana (referee) ; Janoušek, Jan (referee) ; Meduna, Alexandr (advisor)
Tato disertační práce představuje a zkoumá nové možnosti paralelního zpracování ve formálních modelech. Zaměřuje se přitom především na paralelní verze skákajících konečných automatů a na normální formy gramatik se zajímavými paralelními vlastnostmi. První část práce popisuje motivaci pro studium paralelního zpracování ve formálních modelech a stručně představuje skákající modely a normální formy gramatik a gramatických systémů. Jsou zde také upřesněny cíle prezentovaného výzkumu. Druhá část práce je zaměřena na prezentaci nových výsledků v oblasti skákajících konečných automatů. Jako první je zde přestaven n-paralelní skákající konečný automat, který rozšiřuje původní model skákajícího konečného automatu a podporu většího množství čtecích hlav. Práce následně studuje sílu tohoto modelu ve dvou rozdílných skákajících módech. Následuje představení dvojitě skákajících konečných automatů, u kterých jsou zkoumány pokročilé skákající módy využívající dvě čtecí hlavy. Kromě síly těchto modelů jsou zde zkoumány i uzávěrové vlastnosti příslušných tříd jazyků. Jako poslední jsou v této části představeny skákající 5'->3' Watson-Crick konečné automaty, které kombinují skákající chování s biologií inspirovanými Watson-Crick konečnými automaty. Opět je zde zkoumána síla tohoto modelu a to i s uvážením rozličných omezujících podmínek. Třetí část práce je zaměřena na prezentaci nových výsledků v oblasti CD gramatických systémů. Jsou zde prezentovaný dva typy transformací, které dokáží převést libovolnou obecnou gramatiku na dvoukomponentový obecný CD gramatický systém velmi redukované a zjednodušené formy. Kromě této významné redukce a zjednodušení prezentuje práce i několik dalších užitečných vlastností souvisejících s těmito systémy. V poslední části textu jsou pak nastíněny možné oblasti využití představených modelů a normálních forem. Práce je následně uzavřena souhrnem dosažených výsledků a závěrečnými poznámkami k dalšímu směřování výzkumu.
|
|
|
Formal Models of Distributed Computation
Soukup, Ondřej ; Horváth,, Géza (referee) ; Rogalewicz, Adam (referee) ; Meduna, Alexandr (advisor)
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.
|
guest ::
