On Simon’s Congruence Closure of a String

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

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

3 Scopus citations


Two strings are Simon’s ∼ k -congruent if they have the same set of subsequences of length at most k. We study the Simon’s congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present an efficient DFA construction that accepts all ∼ k -congruent strings with respect to w. We also present lower bounds for the state complexity of the Simon’s congruence closure. Finally, we design a polynomial-time algorithm that answers the following open problem: “given a string w over a fixed-sized alphabet, an integer k and a (regular or context-free) language L, decide whether there exists a string v∈ L such that w∼ kv.” The problem is NP-complete for a variable-sized alphabet.

Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems - 24th IFIP WG 1.02 International Conference, DCFS 2022, Proceedings
EditorsYo-Sub Han, György Vaszil
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages15
ISBN (Print)9783031132568
StatePublished - 2022
Event24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 - Debrecen, Hungary
Duration: 29 Aug 202231 Aug 2022

Publication series

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


Conference24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022


  • Finite automata
  • Shortlex normal forms
  • Simon’s congruence
  • State complexity


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

Cite this