Original title: Alternující skákající automaty a jejich aplikace
Translated title: Alternating Jumping Automata and Their Applications
Authors: Nejedlý, Dominik ; Křivka, Zbyněk (referee) ; Meduna, Alexandr (advisor)
Document type: Bachelor's theses
Year: 2022
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Tato práce zavádí alternující skákající automaty a zkoumá některé jejich vlastnosti a vyjadřovací možnosti. Tyto automaty se podobně jako klasické skákající automaty vyznačují schopností nespojitého zpracovávání vstupních řetězců. Po každém jednom čtení symbolů provádí skok na nejvzdálenější místo ve vstupní pásce od aktuální pozice čtecí hlavy a od tam následně v procesu přijímání pokračují. Výchozí počáteční pozicí čtecí hlavy je levý okraj vstupní pásky. Práce demonstruje vliv různých počátečních konfigurací na výpočetní sílu těchto automatů a na základě nově představených převodových algoritmů dokazuje ekvivalenci jejich určitých verzí s lineárními gramatikami. Součástí této práce je potom také porovnání alternujících skákajících automatů s Watson-Crick automaty, ukázka rozdílného přístupu obou těchto modelů k detekci struktury DNA a koncept automatu kombinujícího jejich přednosti. 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.
Keywords: alternating jumping finite automata; DNA structure detection; jumping finite automata; linear languages; simple linear grammar; Watson-Crick automata; alternující skákající konečné automaty; detekce struktury DNA; jednoduchá lineární gramatika; lineární jazyky; skákající konečné automaty; Watson-Crick automaty

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/207297

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


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