On the Simon’s Congruence Neighborhood of Languages

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 27th International Conference, DLT 2023, Proceedings
EditorsFrank Drewes, Mikhail Volkov
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages14
ISBN (Print)9783031332630
StatePublished - 2023
Event27th International Conference on Developments in Language Theory, DLT 2023 - Umeå, Sweden
Duration: 12 Jun 202316 Jun 2023

Publication series

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


Conference27th International Conference on Developments in Language Theory, DLT 2023


  • Simon’s congruence
  • computational complexity
  • congruence relation
  • k-piecewise testable languages


Dive into the research topics of 'On the Simon’s Congruence Neighborhood of Languages'. Together they form a unique fingerprint.

Cite this