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 contribution

3 Citations (Scopus)

Abstract

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
Pages127-141
Number of pages15
ISBN (Print)9783031132568
DOIs
Publication statusPublished - 2022
Event24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022 - Debrecen, Hungary
Duration: 2022 Aug 292022 Aug 31

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

Conference

Conference24th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems, DCFS 2022
Country/TerritoryHungary
CityDebrecen
Period22/8/2922/8/31

Bibliographical note

Publisher Copyright:
© 2022, IFIP International Federation for Information Processing.

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this