On the Simon’s Congruence Neighborhood of Languages
Published:
Contribution
A new exciting result on Simon’s congruence. The paper is a result of the visiting research in Canada in Summer 2022.
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 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.
Recommended citation:
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko, and Kai Salomaa. “On the Simon’s Congruence Neighborhood of Languages.” International Conference on Developments in Language Theory (DLT), 2023.