On the Simon’s Congruence Neighborhood of Languages

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

doi:10.1007/978-3-031-33264-7_14

On the Simon’s Congruence Neighborhood of Languages

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

College of Computing

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

4 Citations (Scopus)

Abstract

Given an integer k, Simon’s congruence relation says that two strings u and v are ∼ _k -congruent if they have the same set of subsequences of length at most k. We extend Simon’s congruence to languages. First, we define the Simon’s congruence neighborhood of a language L to be a set of strings that have a ∼ _k -congruent string in L. Next, we define two languages L₁ and L₂ to be ≡ _k -congruent if both have the same Simon’s congruence neighborhood. We prove that it is PSPACE-complete to check ≡ _k -congruence of two regular languages and decidable up to recursive languages. Moreover, we tackle the problem of computing the maximum k that makes two given languages ≡ _k -congruent. This problem is PSPACE-complete for two regular languages, and undecidable for context-free languages.

Original language	English
Title of host publication	Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings
Editors	Frank Drewes, Mikhail Volkov
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	168-181
Number of pages	14
ISBN (Print)	9783031332630
DOIs	https://doi.org/10.1007/978-3-031-33264-7_14
Publication status	Published - 2023
Event	27th International Conference on Developments in Language Theory, DLT 2023 - Umeå, Sweden Duration: 2023 Jun 12 → 2023 Jun 16

Publication series

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

Conference

Conference	27th International Conference on Developments in Language Theory, DLT 2023
Country/Territory	Sweden
City	Umeå
Period	23/6/12 → 23/6/16

Bibliographical note

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-33264-7_14

Cite this

Kim, S., Han, Y. S., Ko, S. K., & Salomaa, K. (2023). On the Simon’s Congruence Neighborhood of Languages. In F. Drewes, & M. Volkov (Eds.), Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings (pp. 168-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13911 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-33264-7_14

Kim, Sungmin ; Han, Yo Sub ; Ko, Sang Ki et al. / On the Simon’s Congruence Neighborhood of Languages. Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. editor / Frank Drewes ; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2023. pp. 168-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2d21f0b9d4fa422f9087e0ab7513710f,

title = "On the Simon{\textquoteright}s Congruence Neighborhood of Languages",

abstract = "Given an integer k, Simon{\textquoteright}s congruence relation says that two strings u and v are ∼ k -congruent if they have the same set of subsequences of length at most k. We extend Simon{\textquoteright}s congruence to languages. First, we define the Simon{\textquoteright}s congruence neighborhood of a language L to be a set of strings that have a ∼ k -congruent string in L. Next, we define two languages L1 and L2 to be ≡ k -congruent if both have the same Simon{\textquoteright}s congruence neighborhood. We prove that it is PSPACE-complete to check ≡ k -congruence of two regular languages and decidable up to recursive languages. Moreover, we tackle the problem of computing the maximum k that makes two given languages ≡ k -congruent. This problem is PSPACE-complete for two regular languages, and undecidable for context-free languages.",

keywords = "Simon{\textquoteright}s congruence, computational complexity, congruence relation, k-piecewise testable languages",

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

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 27th International Conference on Developments in Language Theory, DLT 2023 ; Conference date: 12-06-2023 Through 16-06-2023",

year = "2023",

doi = "10.1007/978-3-031-33264-7_14",

language = "English",

isbn = "9783031332630",

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 = "168--181",

editor = "Frank Drewes and Mikhail Volkov",

booktitle = "Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings",

address = "Germany",

}

Kim, S, Han, YS, Ko, SK & Salomaa, K 2023, On the Simon’s Congruence Neighborhood of Languages. in F Drewes & M Volkov (eds), Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13911 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 168-181, 27th International Conference on Developments in Language Theory, DLT 2023, Umeå, Sweden, 23/6/12. https://doi.org/10.1007/978-3-031-33264-7_14

On the Simon’s Congruence Neighborhood of Languages. / Kim, Sungmin; Han, Yo Sub; Ko, Sang Ki et al.
Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. ed. / Frank Drewes; Mikhail Volkov. Springer Science and Business Media Deutschland GmbH, 2023. p. 168-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13911 LNCS).

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

TY - GEN

T1 - On the Simon’s Congruence Neighborhood of Languages

AU - Kim, Sungmin

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2023

Y1 - 2023

N2 - Given an integer k, Simon’s congruence relation says that two strings u and v are ∼ k -congruent if they have the same set of subsequences of length at most k. We extend Simon’s congruence to languages. First, we define the Simon’s congruence neighborhood of a language L to be a set of strings that have a ∼ k -congruent string in L. Next, we define two languages L1 and L2 to be ≡ k -congruent if both have the same Simon’s congruence neighborhood. We prove that it is PSPACE-complete to check ≡ k -congruence of two regular languages and decidable up to recursive languages. Moreover, we tackle the problem of computing the maximum k that makes two given languages ≡ k -congruent. This problem is PSPACE-complete for two regular languages, and undecidable for context-free languages.

AB - Given an integer k, Simon’s congruence relation says that two strings u and v are ∼ k -congruent if they have the same set of subsequences of length at most k. We extend Simon’s congruence to languages. First, we define the Simon’s congruence neighborhood of a language L to be a set of strings that have a ∼ k -congruent string in L. Next, we define two languages L1 and L2 to be ≡ k -congruent if both have the same Simon’s congruence neighborhood. We prove that it is PSPACE-complete to check ≡ k -congruence of two regular languages and decidable up to recursive languages. Moreover, we tackle the problem of computing the maximum k that makes two given languages ≡ k -congruent. This problem is PSPACE-complete for two regular languages, and undecidable for context-free languages.

KW - Simon’s congruence

KW - computational complexity

KW - congruence relation

KW - k-piecewise testable languages

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

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

U2 - 10.1007/978-3-031-33264-7_14

DO - 10.1007/978-3-031-33264-7_14

M3 - Conference contribution

AN - SCOPUS:85161134322

SN - 9783031332630

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

SP - 168

EP - 181

BT - Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings

A2 - Drewes, Frank

A2 - Volkov, Mikhail

PB - Springer Science and Business Media Deutschland GmbH

T2 - 27th International Conference on Developments in Language Theory, DLT 2023

Y2 - 12 June 2023 through 16 June 2023

ER -

Kim S, Han YS, Ko SK, Salomaa K. On the Simon’s Congruence Neighborhood of Languages. In Drewes F, Volkov M, editors, Developments in Language Theory - 27th International Conference, DLT 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 168-181. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-33264-7_14