Thesis Details

Alternující skákající automaty a jejich aplikace

Bachelor's Thesis Student: Nejedlý Dominik Academic Year: 2021/2022 Supervisor: Meduna Alexander, prof. RNDr., CSc.
English title
Alternating Jumping Automata and Their Applications
Language
Czech
Abstract

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

jumping finite automata, alternating jumping finite automata, linear languages, simple linear grammar, Watson-Crick automata, DNA structure detection

Department
Degree Programme
Files
Status
defended, grade A
Date
13 June 2022
Reviewer
Committee
Vojnar Tomáš, prof. Ing., Ph.D. (DITS FIT BUT), předseda
Grézl František, Ing., Ph.D. (DCGM FIT BUT), člen
Martínek Tomáš, 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
Citation
NEJEDLÝ, Dominik. Alternující skákající automaty a jejich aplikace. Brno, 2022. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2022-06-13. Supervised by Meduna Alexander. Available from: https://www.fit.vut.cz/study/thesis/25068/
BibTeX
@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/"
}
Back to top