Consensus string problem for multiple regular languages

Yo Sub Han; Sang Ki Ko; Timothy Ng; Kai Salomaa

doi:10.1007/978-3-319-53733-7_14

Consensus string problem for multiple regular languages

Yo Sub Han, Sang Ki Ko, Timothy Ng, Kai Salomaa

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

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 L₁, ⋯, L_k to be within distance at most r to some string in each of the languages L₁, ⋯, L_k. 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.

Original language	English
Title of host publication	Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings
Editors	Frank Drewes, Carlos Martín-Vide, Bianca Truthe
Publisher	Springer Verlag
Pages	196-207
Number of pages	12
ISBN (Print)	9783319537320
DOIs	https://doi.org/10.1007/978-3-319-53733-7_14
Publication status	Published - 2017
Event	11th International Conference on Language and Automata Theory and Applications, LATA 2017 - Umea, Sweden Duration: 2017 Mar 6 → 2017 Mar 9

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10168 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	11th International Conference on Language and Automata Theory and Applications, LATA 2017
Country/Territory	Sweden
City	Umea
Period	17/3/6 → 17/3/9

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG 2017.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-53733-7_14

Cite this

Han, Y. S., Ko, S. K., Ng, T., & Salomaa, K. (2017). Consensus string problem for multiple regular languages. In F. Drewes, C. Martín-Vide, & B. Truthe (Eds.), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings (pp. 196-207). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-53733-7_14

Han, Yo Sub ; Ko, Sang Ki ; Ng, Timothy et al. / Consensus string problem for multiple regular languages. Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. editor / Frank Drewes ; Carlos Martín-Vide ; Bianca Truthe. Springer Verlag, 2017. pp. 196-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a636e5cc5c6c43459375866a5964ddf7,

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",

}

Han, YS, Ko, SK, Ng, T & Salomaa, K 2017, Consensus string problem for multiple regular languages. in F Drewes, C Martín-Vide & B Truthe (eds), Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10168 LNCS, Springer Verlag, pp. 196-207, 11th International Conference on Language and Automata Theory and Applications, LATA 2017, Umea, Sweden, 17/3/6. https://doi.org/10.1007/978-3-319-53733-7_14

Consensus string problem for multiple regular languages. / Han, Yo Sub; Ko, Sang Ki; Ng, Timothy et al.
Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. ed. / Frank Drewes; Carlos Martín-Vide; Bianca Truthe. Springer Verlag, 2017. p. 196-207 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10168 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Consensus string problem for multiple regular languages

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Ng, Timothy

AU - Salomaa, Kai

N1 - Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Consensus string problem

KW - Edit-distance

KW - Regular languages

UR - http://www.scopus.com/inward/record.url?scp=85013409453&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85013409453&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-53733-7_14

DO - 10.1007/978-3-319-53733-7_14

M3 - Conference contribution

AN - SCOPUS:85013409453

SN - 9783319537320

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 196

EP - 207

BT - Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings

A2 - Drewes, Frank

A2 - Martín-Vide, Carlos

A2 - Truthe, Bianca

PB - Springer Verlag

T2 - 11th International Conference on Language and Automata Theory and Applications, LATA 2017

Y2 - 6 March 2017 through 9 March 2017

ER -

Han YS, Ko SK, Ng T, Salomaa K. Consensus string problem for multiple regular languages. In Drewes F, Martín-Vide C, Truthe B, editors, Language and Automata Theory and Applications - 11th International Conference, LATA 2017, Proceedings. Springer Verlag. 2017. p. 196-207. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-53733-7_14

Consensus string problem for multiple regular languages

Abstract

Publication series

Other

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this