On Simon’s Congruence Closure of a String

Sungmin Kim; Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-031-13257-5_10

On Simon’s Congruence Closure of a String

Sungmin Kim, Yo Sub Han, Sang Ki Ko, Kai Salomaa

Department of Artificial Intelligence

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

3 Scopus citations

Abstract

Two strings are Simon’s ∼ _k -congruent if they have the same set of subsequences of length at most k. We study the Simon’s congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present an efficient DFA construction that accepts all ∼ _k -congruent strings with respect to w. We also present lower bounds for the state complexity of the Simon’s congruence closure. Finally, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether there exists a string v∈ L such that w∼ _kv.” The problem is NP-complete for a variable-sized alphabet.

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings
Editors	Yo-Sub Han, György Vaszil
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	127-141
Number of pages	15
ISBN (Print)	9783031132568
DOIs	https://doi.org/10.1007/978-3-031-13257-5_10
State	Published - 2022
Event	24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 - Debrecen, Hungary Duration: 29 Aug 2022 → 31 Aug 2022

Publication series

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

Conference

Conference	24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022
Country/Territory	Hungary
City	Debrecen
Period	29/08/22 → 31/08/22

Keywords

Finite automata
Shortlex normal forms
Simon’s congruence
State complexity

Access to Document

10.1007/978-3-031-13257-5_10

Cite this

Kim, S., Han, Y. S., Ko, S. K., & Salomaa, K. (2022). On Simon’s Congruence Closure of a String. In Y.-S. Han, & G. Vaszil (Eds.), Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings (pp. 127-141). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13439 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-13257-5_10

Kim, Sungmin ; Han, Yo Sub ; Ko, Sang Ki et al. / On Simon’s Congruence Closure of a String. Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings. editor / Yo-Sub Han ; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2022. pp. 127-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a7f7f412eec9450b985d50019f94d0ae,

title = "On Simon{\textquoteright}s Congruence Closure of a String",

abstract = "Two strings are Simon{\textquoteright}s ∼ k -congruent if they have the same set of subsequences of length at most k. We study the Simon{\textquoteright}s congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present an efficient DFA construction that accepts all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of the Simon{\textquoteright}s congruence closure. Finally, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether there exists a string v∈ L such that w∼ kv.” The problem is NP-complete for a variable-sized alphabet.",

keywords = "Finite automata, Shortlex normal forms, Simon{\textquoteright}s congruence, State complexity",

author = "Sungmin Kim and Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} 2022, IFIP International Federation for Information Processing.; 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 ; Conference date: 29-08-2022 Through 31-08-2022",

year = "2022",

doi = "10.1007/978-3-031-13257-5_10",

language = "English",

isbn = "9783031132568",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "127--141",

editor = "Yo-Sub Han and Gy{\"o}rgy Vaszil",

booktitle = "Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings",

address = "Germany",

}

Kim, S, Han, YS, Ko, SK & Salomaa, K 2022, On Simon’s Congruence Closure of a String. in Y-S Han & G Vaszil (eds), Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13439 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 127-141, 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022, Debrecen, Hungary, 29/08/22. https://doi.org/10.1007/978-3-031-13257-5_10

On Simon’s Congruence Closure of a String. / Kim, Sungmin; Han, Yo Sub; Ko, Sang Ki et al.
Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings. ed. / Yo-Sub Han; György Vaszil. Springer Science and Business Media Deutschland GmbH, 2022. p. 127-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13439 LNCS).

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

TY - GEN

T1 - On Simon’s Congruence Closure of a String

AU - Kim, Sungmin

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2022

Y1 - 2022

N2 - Two strings are Simon’s ∼ k -congruent if they have the same set of subsequences of length at most k. We study the Simon’s congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present an efficient DFA construction that accepts all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of the Simon’s congruence closure. Finally, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether there exists a string v∈ L such that w∼ kv.” The problem is NP-complete for a variable-sized alphabet.

AB - Two strings are Simon’s ∼ k -congruent if they have the same set of subsequences of length at most k. We study the Simon’s congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present an efficient DFA construction that accepts all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of the Simon’s congruence closure. Finally, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether there exists a string v∈ L such that w∼ kv.” The problem is NP-complete for a variable-sized alphabet.

KW - Finite automata

KW - Shortlex normal forms

KW - Simon’s congruence

KW - State complexity

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

U2 - 10.1007/978-3-031-13257-5_10

DO - 10.1007/978-3-031-13257-5_10

M3 - Conference contribution

AN - SCOPUS:85137045127

SN - 9783031132568

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

SP - 127

EP - 141

BT - Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings

A2 - Han, Yo-Sub

A2 - Vaszil, György

PB - Springer Science and Business Media Deutschland GmbH

T2 - 24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022

Y2 - 29 August 2022 through 31 August 2022

ER -

Kim S, Han YS, Ko SK, Salomaa K. On Simon’s Congruence Closure of a String. In Han YS, Vaszil G, editors, Descriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 127-141. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-13257-5_10