On the Simon’s congruence neighborhood of languages

Sungmin Kim, Yo-Sub Han, Sang-Ki Ko and Kai Salomaa.
Presented at DLT'23.

[Link to paper]

Definitions

Simon’s congruence: For an integer $k$, two strings $w_1$ and $w_2$ are $k$-congruent ($w_1\sim_k w_2$) if they have the same set of subsequences of at most $k$.
The Simon’s congruence neighborhood of a language $L$: the set of strings that are $k$-congruent to some string in $L$.

Summary of results

• PSPACE-completeness results for the following decision problems for two given regular languages:
  • Finiteness of the supremum of $k$ that allows equivalence of the Simon's congruence neighborhoods
  • Inclusion and equivalence of the Simon's congruence neighborhoods for a given $k$
• Undecidability of computing the maximum $k$ that allows equivalence of the Simon's congruence neighborhoods for input context-free languages
• Decidability of inclusion and equivalence of the Simon's congruence neighborhoods for a given $k$, up to input recursive languages

Keywords Simon’s congruence, neighborhoods, algorithmic complexity, Savitch’s theorem