On Parallel Processing in Formal Models: Jumping Automata and Normal Forms

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.The present thesis introduces and studies new possibilities of parallel processing in formal models. More specifically, it focuses its attention on parallel versions of jumping finite automata and on normal forms of grammars with interesting parallel properties. In the first part of this thesis, we give an initial motivation for studying parallel processing in formal models. We briefly introduce jumping models and normal forms of grammars and grammar systems. Finally, we state the precise focus and goals of our research. The second part of this thesis is focused on new results on jumping finite automata. First, we introduce n-parallel jumping finite automata that enhance the original jumping finite automaton model with multiple reading heads. The rest of the chapter then studies the accepting power of the model under two different jumping modes. Second, we introduce double-jumping finite automata and explore advanced jumping modes utilizing two heads. We study the accepting power of the models and also the closure properties of the related language families. Lastly, we introduce jumping 5'->3' Watson-Crick finite automata that combine the jumping behavior with the biology-inspired Watson-Crick finite automata that process double-stranded DNA sequences. The rest of this chapter then studies the accepting power of the model under unrestricted and various restricted conditions. The third part of this thesis is focused on new results on CD grammar systems. We introduce two types of transformations that turn arbitrary general grammars into equivalent two-component general CD grammar systems of very reduced and simplified forms. Apart from the reduction and simplification, we describe several other useful properties concerning these systems and the way they work. In the last part, we mention possible application perspectives for the introduced models and normal forms, and we conclude the thesis with the final summary and the description of theoretical perspectives for the achieved results.