טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBen Bassat Ran
SubjectParameterized Automata Constructions and Their Applications
DepartmentDepartment of Computer Science
Supervisor Professor Hadas Shachnai
Full Thesis textFull thesis text - English Version


Abstract

In this work, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k-Distinct language, defined as the set of words of length k over the alphabet, whose symbols are all distinct. This language is implicitly related to several breakthrough techniques developed during the last two decades, to design parameterized algorithms for fundamental problems such as k-Path and r-Dimensional k-Matching. Building upon the well-known color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for k-Distinct. We develop non-deterministic automata (NFAs) of sizes 4k(k) nO(1) and (2e)k(k) nO(1), where the latter satisfies a `bounded ambiguity' property relevant to approximate counting, as well as a nondeterministic xor automaton (NXA) of size 2k nO(1), where n is the size of the alphabet. We show that our constructions can be used to develop both deterministic and randomized algorithms for k-Path, r-Dimensional k-Matching and Module Motif in a natural manner, considering also their approximate counting variants. Our framework is modular and consists of two parts: designing an automaton for k-Distinct, and designing a problem specific automaton, as well as an algorithm for deciding whether the intersection automaton's language is empty, or for counting the number of accepting paths in it.