## Abstract

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 language | English |
---|---|

Pages (from-to) | 144-154 |

Number of pages | 11 |

Journal | Theoretical Computer Science |

Volume | 862 |

DOIs | |

State | Published - 16 Mar 2021 |

## Keywords

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