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 Lk(Σ)⊆Σk, defined as the set of words of length k over an 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-Dimensionalk-Matching. Building upon the color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for Lk(Σ). 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 non-deterministic xor automaton (NXA) of size 2k⋅nO(1), where n=|Σ|. We show that our constructions can be used to develop both deterministic and randomized algorithms for k-Path, r-Dimensionalk-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.