Název: Alternující skákající automaty a jejich aplikace
Překlad názvu: Alternating Jumping Automata and Their Applications
Autoři: Nejedlý, Dominik ; Křivka, Zbyněk (oponent) ; Meduna, Alexandr (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2022
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [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.
Klíčová slova: 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; alternating jumping finite automata; DNA structure detection; jumping finite automata; linear languages; simple linear grammar; Watson-Crick automata

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/207297

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-599793


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce