On Simon's congruence closure of a string

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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Two strings are Simon's ∼k-congruent if they have the same set of subsequences of length at most k. We study Simon's congruence closure of a string, which is regular by definition. Given a string w over an alphabet Σ, we present two efficient DFA constructions that accept all ∼k-congruent strings with respect to w. We also present lower bounds for the state complexity of Simon's congruence closure. Then, 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 or not there exists a string v∈L such that w∼kv.” In addition, for a variable-sized alphabet, we prove that the problem is NP-complete.

Original languageEnglish
Article number114078
JournalTheoretical Computer Science
Volume972
DOIs
StatePublished - 13 Sep 2023

Keywords

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

Fingerprint

Dive into the research topics of 'On Simon's congruence closure of a string'. Together they form a unique fingerprint.

Cite this