Closest substring problems for regular languages

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

Authors

• Yo-Sub Han
• Sang-Ki Ko
• Timothy Ng
• Kai Salomaa

Keywords

• Closest substring problem
• Regular languages
• Finite automata
• Edit distance
• Computational complexity