Thesis Details

Beyond Register Automata: Pushing the Border of Decidability

Bachelor's Thesis Student: Gulčíková Sabína Academic Year: 2021/2022 Supervisor: Lengál Ondřej, Ing., Ph.D.
Czech title
Za registrovými automaty: posouvání hranic rozhodnutelnosti
Language
English
Abstract

Register automaton (RA) operating over infinite alphabet is one of the great tools for pattern matching with backreferences, runtime verification, or modelling of parallel computation. In case of pattern matching with backreferences, the state-of-the-art matchers make use of backtracking algorithms, whose application causes significant slowdown in case of nondeterministic regular expressions. Since RAs cannot always be determinised, it is an unsuitable model for solution to problems related to inefficient usage of backtracking algorithms. On the other hand, the RA's quality of being equipped by a finite memory serves as a good basis for storing the so-called capture groups used in pattern matching with backreferences. In this work, a formal model called register set automaton (RsA) is proposed. A large class of RAs can be transformed into this deterministic model, which, among other things, allows for fast pattern matching with backreferences. We explore RsA's properties including decidability of emptiness testing, determinisability, closure under Boolean operations and we compare it to other register models in context of their expressive power.

Keywords

finite memory automata, register automata, infinite alphabet, regular expressions, regular expressions with backreferences, language inclusion of register automata

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
GULČÍKOVÁ, Sabína. Beyond Register Automata: Pushing the Border of Decidability. Brno, 2022. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2022-06-13. Supervised by Lengál Ondřej. Available from: https://www.fit.vut.cz/study/thesis/24443/
BibTeX
@bachelorsthesis{FITBT24443,
    author = "Sab\'{i}na Gul\v{c}\'{i}kov\'{a}",
    type = "Bachelor's thesis",
    title = "Beyond Register Automata: Pushing the Border of Decidability",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2022,
    location = "Brno, CZ",
    language = "english",
    url = "https://www.fit.vut.cz/study/thesis/24443/"
}
Back to top