The k-distinct language: Parameterized automata constructions

In this paper, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k-DISTINCT language L-k(Sigma) subset of Sigma(k), defined as the set of words of length k over an alphabet Sigma 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 color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for L-k(Sigma). We develop non-deterministic automata (NFAs) of sizes 4(k+0(k)).n(0(1)) and (2e)(k+0(k)).n(0(1)), where the latter satisfies a 'bounded ambiguity' property relevant to approximate counting, as well as a non-deterministic xor automaton (NXA) of size 2(k).n(0(1)), where n = vertical bar Sigma vertical bar 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. (C) 2016 Elsevier B.V. All rights reserved.