Thesis Details
Alternující skákající automaty a jejich aplikace
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, alternating jumping finite automata, linear languages, simple linear grammar, Watson-Crick automata, DNA structure detection
Grézl František, Ing., Ph.D. (DCGM FIT BUT), člen
Martínek Tomáš, doc. Ing., Ph.D. (DCSY FIT BUT), člen
Peringer Petr, Dr. Ing. (DITS FIT BUT), člen
Ryšavý Ondřej, doc. Ing., Ph.D. (DIFS FIT BUT), člen
@bachelorsthesis{FITBT25068, author = "Dominik Nejedl\'{y}", type = "Bachelor's thesis", title = "Alternuj\'{i}c\'{i} sk\'{a}kaj\'{i}c\'{i} automaty a jejich aplikace", school = "Brno University of Technology, Faculty of Information Technology", year = 2022, location = "Brno, CZ", language = "czech", url = "https://www.fit.vut.cz/study/thesis/25068/" }