@inproceedings{10b84b9f56f04a8c8923a769f2dc6dc4,
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",
}