Technical Report MSC-2015-03

TR#:MSC-2015-03
Class:MSC
Title: Parameterized Automata Constructions and Their Applications
Authors: Ran Ben Basat
Supervisors: Hadas Shachnai
PDFCurrently accessibly only within the Technion network
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+o(k) nO(1) and (2e)k+o(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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2015/MSC/MSC-2015-03), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2015
To the main CS technical reports page

Computer science department, Technion
admin