@inproceedings{3382f9c03dcb47acb58c39c6bc656ae6,
title = "Consensus string problem for multiple regular languages",
abstract = "The consensus string (or center string, closest string) of a set S of strings is defined as a string which is within a radius r from all strings in S. It is well-known that the consensus string problem for a finite set of equal-length strings is NP-complete. We study the consensus string problem for multiple regular languages. We define the consensus string of languages L1, ⋯, Lk to be within distance at most r to some string in each of the languages L1, ⋯, Lk. We also study the complexity of some parameterized variants of the consensus string problem. For a constant k, we give a polynomial time algorithm for the consensus string problem for k regular languages using additive weighted finite automata. We show that the consensus string problem for multiple regular languages becomes intractable when k is not fixed. We also examine the case when the length of the consensus string is given as part of input.",
keywords = "Computational complexity, Consensus string problem, Edit-distance, Regular languages",
author = "Han, {Yo Sub} and Ko, {Sang Ki} and Timothy Ng and Kai Salomaa",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 11th International Conference on Language and Automata Theory and Applications, LATA 2017 ; Conference date: 06-03-2017 Through 09-03-2017",
year = "2017",
doi = "10.1007/978-3-319-53733-7_14",
language = "English",
isbn = "9783319537320",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "196--207",
editor = "Frank Drewes and Carlos Mart{\'i}n-Vide and Bianca Truthe",
booktitle = "Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings",
address = "Germany",
}