|
|
Alternating Jumping Automata and Their Applications
Nejedlý, Dominik ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
This thesis proposes alternating jumping automata and investigates some of their properties and expressive capabilities. These automata, like classical jumping ones, are characterized by the ability to process input strings discontinuously. After each single reading of symbols, they perform a jump to the farthest position in the input tape from the current position of the reading head and continue the computation from there. The default starting position of the reading head is the left edge of the input tape. The thesis demonstrates the effect of different initial configurations on the computational power of these automata and proves the equivalence of certain versions of them with linear grammars using newly introduced conversion algorithms. This thesis also includes a comparison of alternating jumping automata with Watson-Crick automata, a demonstration of the different approaches of these two models to DNA structure detection, and a concept of an automaton combining their benefits.
|
|
|
Jumping Finite Automata and Transducers
Hrubý, Juraj ; Burgetová, Ivana (referee) ; Meduna, Alexandr (advisor)
The bachelor's thesis builds upon the study of jumping finite automata and introduces jumping finite transducers. Jumping finite automata are finite automata modified in such a way that symbols from the input tape are not read continuously from left to right but that the reading head can make moves on the input tape by jumps. Jumping finite transducers are finite transducers modified in a very similar way. In order to implement jumping finite automata and transducers, strictly deterministic versions of them were introduced by restricting the finite state control and by modification of the binary jumping relation. The thesis furthermore focuses on possible usage of jumping finite automata and transducers and on the description of the implementation of strictly deterministic jumping finite automata.
|
|
|
Regulated Language Operations and Their Use
Chocholatý, David ; Kožár, Tomáš (referee) ; Meduna, Alexandr (advisor)
This thesis introduces and studies erasing systems as an alternative formal language model to general jumping finite automata. A significant difference compared to the given automata is the use of a control regular language instead of state control in the form of a general finite automaton. Erasing systems leave the string work on the input tape, whereas regular languages themselves can be accepted by classical finite automata. At the same time, with the introduction of a new formal system, the thesis demonstrates its relations with well-known language families, the family of shuffle languages, Dyck languages and closure properties. Based on the formal specification of the erasing system, multiple applications in bioinformatics for molecular biology, text editors and compositional chess are shown, including designing algorithms and presenting the implementation solution.
|
|
|
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.
|
|
|
Alternating Jumping Automata and Their Applications
Nejedlý, Dominik ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
This thesis proposes alternating jumping automata and investigates some of their properties and expressive capabilities. These automata, like classical jumping ones, are characterized by the ability to process input strings discontinuously. After each single reading of symbols, they perform a jump to the farthest position in the input tape from the current position of the reading head and continue the computation from there. The default starting position of the reading head is the left edge of the input tape. The thesis demonstrates the effect of different initial configurations on the computational power of these automata and proves the equivalence of certain versions of them with linear grammars using newly introduced conversion algorithms. This thesis also includes a comparison of alternating jumping automata with Watson-Crick automata, a demonstration of the different approaches of these two models to DNA structure detection, and a concept of an automaton combining their benefits.
|
|
| |
|
|
Jumping Finite Automata and Transducers
Hrubý, Juraj ; Burgetová, Ivana (referee) ; Meduna, Alexandr (advisor)
The bachelor's thesis builds upon the study of jumping finite automata and introduces jumping finite transducers. Jumping finite automata are finite automata modified in such a way that symbols from the input tape are not read continuously from left to right but that the reading head can make moves on the input tape by jumps. Jumping finite transducers are finite transducers modified in a very similar way. In order to implement jumping finite automata and transducers, strictly deterministic versions of them were introduced by restricting the finite state control and by modification of the binary jumping relation. The thesis furthermore focuses on possible usage of jumping finite automata and transducers and on the description of the implementation of strictly deterministic jumping finite automata.
|
guest ::
