Closest substring problems for regular languages

Yo Sub Han, Sang Ki Ko, Timothy Ng, Kai Salomaa

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)144-154
Number of pages11
JournalTheoretical Computer Science
StatePublished - 16 Mar 2021


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


Dive into the research topics of 'Closest substring problems for regular languages'. Together they form a unique fingerprint.

Cite this