Closest substring problems for regular languages

The problem asks whether there exists a consensus string of given length such that each string in a set of strings has a substring whose edit distance is at most (called the radius) from . The problem has been studied for finite sets of strings and is known to be -hard. We show that the problem for regular languages represented by nondeterministic finite automata (NFA) is -complete. The problem remains -hard even when the input is a deterministic finite automaton and the length and radius are given in unary. Also we show that the problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both -hard and -hard.