M.Sc Student | Ben Bassat Ran |
---|---|

Subject | Parameterized Automata Constructions and Their Applications |

Department | Department of Computer Science |

Supervisor | Professor Hadas Shachnai |

Full Thesis text |

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 4^{k}^{(k)}
*n*^{O(1)} and (2*e*)^{k}^{(k)}
*n*^{O(1)}, where the latter satisfies a `bounded ambiguity'
property relevant to approximate counting, as well as a nondeterministic xor
automaton (NXA) of size 2^{k}*n*^{O(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.