On Simon’s Congruence Closure of a String
Published:
Summary
Read the abstract.
Contribution
This is my first accepted conference paper! I am the main author for this paper.
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.
Recommended citation:
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko, and Kai Salomaa. “On Simon’s Congruence Closure of a String.” International Conference on Descriptional Complexity of Formal Systems (DCFS), pp.127–141, 2022.