Consensus String Problem for Multiple Regular Languages



Han, Yo-Sub, Ko, Sang-Ki, Ng, Timothy and Salomaa, Kai
(2017) Consensus String Problem for Multiple Regular Languages. .

[img] 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