@inproceedings{368e4f66eb554aefb24e570846a00267,

title = "Closest Substring Problems for Regular Languages",

abstract = "It is well known that given a finite set of strings of equal length, the Consensus String problem—the problem of deciding whether or not there exists a consensus string whose distance is at most r from every string in the given set—is proven to be NP-complete. A similar problem called the Closest Substring problem asks whether there exists a string w of length l such that each string in a given set L has a substring whose distance is at most r (called radius) from w. As the Closest Substring problem is a generalized version of the Consensus String problem, it is obvious that the problem is NP-hard for a finite set of strings. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFAs) is PSPACE-complete. The main difference from the previous work is that we consider an infinite set of strings, which is recognized by an NFA as input instead of a finite set of strings. We also prove that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy (formula presented) and is both NP-hard and coNP-hard.",

keywords = "Closest substring problem, Computational complexity, Edit distance, Regular languages",

author = "Han, {Yo Sub} and Ko, {Sang Ki} and Timothy Ng and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 22nd International Conference on Developments in Language Theory, DLT 2018 ; Conference date: 10-09-2018 Through 14-09-2018",

year = "2018",

doi = "10.1007/978-3-319-98654-8_32",

language = "English",

isbn = "9783319986531",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "392--403",

editor = "Mizuho Hoshi and Shinnosuke Seki",

booktitle = "Developments in Language Theory - 22nd International Conference, DLT 2018, Proceedings",

address = "Germany",

}