Tore Koss

collaborators

2 papers

cs.DS2020

The Edit Distance to $k$ -Subsequence Universality

Pamela Fleischmann, Maria Kosche, Tore Koß +2

A word $u$ is a subsequence of another word $w$ if $u$ can be obtained from $w$ by deleting some of its letters. The word $w$ with alph $(w) = Σ$ is called $k$ -subsequence universal i…

cs.FL2020

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…

The Edit Distance to k-Subsequence Universality

Efficiently Testing Simon's Congruence

The Edit Distance to $k$ -Subsequence Universality