Efficiently Testing Simon's Congruence

Pawel Gawrychowski, Maria Kosche, Tore Koss +2

Simon's congruence ${\sim }_k$ is defined as follows: two words are ${\sim }_k$-equivalent if they have the same set of subsequences of length at most $k$. We propose an algorithm which…