Meno:  Matúą


Priezvisko:  Juran


Názov:  Longest Shortest Words in Regular Languages


Vedúci:  RNDr. Peter Kostolányi, PhD.


Rok:  2021


Kµúčové slová:  shortest word, rotating finite automaton, alternating finite automaton


Abstrakt:  In this thesis, we study the following problem: given an automaton with a given number of states, how long can the shortest accepted word potentially be? This problem was studied in the past in the case of nondeterministic finite automata and twoway automata. We provide an overview of relevant previous results and define the function lsw which generalizes this problem to sequences of finite sets of languages. Then, we study the problem with rotating finite automata and alternating finite automata as models of choice. We describe lower and upper bounds for accepted languages, their intersections and complements for alphabets of various sizes. Lastly, we compare the values that the function lsw attains for sequences defined by certain models.

