On Simon’s congruence closure of a string
Sungmin Kim, Yo-Sub Han, Sang-Ki Ko and Kai Salomaa.
Presented at DCFS'22.
Presented at DCFS'22.
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$.
Simon’s congruence closure:
$\texttt{Closure}_k(w)$ consists of the strings
that are $k$-congruent to $w$.
Summary of results
- A DFA construction for $\texttt{Closure}_k(w)$
- A lower bound for the number of states in a DFA for $\texttt{Closure}_k(w)$
- A polynomial-time algorithm for the following problem: given a string $w$ and a context-free language $L$ over a fixed-sized alphabet, decide whether or not there exists a string in $L$ that is $k$-congruent to $w$
- An NP-completeness proof for the same problem over variable-sized alphabets
Keywords
Simon’s congruence, state complexity, finite automata, shortlex normal forms