Maria Kosche

activity

20172023

most citedEfficiently Testing Simon's Congruence

8 citations · 10 across the 5 of their papers we have counts for

collaborators

Showing 2020Show all

2 papers · 1 filter

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★ 8 cited

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