Han, Yo-Sub, Ko, Sang-Ki, Ng, Timothy and Salomaa, Kai
(2017)
Consensus String Problem for Multiple Regular Languages.
.
Text
consensus_LATA.pdf - Author Accepted Manuscript Download (108kB) |
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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | Consensus string problem, Computational complexity, Regular languages, Edit-distance |
Depositing User: | Symplectic Admin |
Date Deposited: | 20 Apr 2017 09:10 |
Last Modified: | 19 Jan 2023 07:06 |
DOI: | 10.1007/978-3-319-53733-7_14 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3007016 |