Field of Study: Computer Science
Student: Peter Grochal [ contact ]
Supervisor: prof. RNDr. Rastislav Královič, PhD.
Email: kralovic at dcs dot fmph dot uniba dot sk
Abstract: This thesis aims to explore the theory of formal languages, focused on randomized automata. In this thesis, we explore one-way multi-head probabilistic finite automata (PFA(k)) with the various models of randomization that are usually studied. We first formally define both Monte-Carlo and LasVegas randomizations, then the various errors, with which such automata can recognize languages. We also define and prove a normal form in which the PFA(k) has to move at least one head at every step of the computation. We then explore the properties of Monte-Carlo and LasVegas PFA(k). For all these models, we prove a hierarchy, that with (k + 1)-heads they have greater expressive power than with k. We also explore various closure properties of classes recognized by these automata, and the relations between these classes. We additionally define a barely-random PFA(k) and show that these probabilistic automata cannot be amplified, i.e., we prove a lower bound on the error with which barely-random PFA(k) can recognize a certain language.
Keywords: formal languages, one-way multi-head probabilistic finite automata, randomized automata, LasVegas randomization, Monte-Carlo randomization, hierarchy, barely-random probabilistic automata, amplification.
Thesis - submitted (EN): [ pdf ]
Thesis - after incorporation of comments (EN): [ pdf ]