Stefan Siemer

collaborators

3 papers

cs.DS2021

Matching Patterns with Variables under Hamming Distance

Paweł Gawrychowski, Florin Manea, Stefan Siemer

A pattern $α$ is a string of variables and terminal letters. We say that $α$ matches a word $w$ , consisting only of terminal letters, if $w$ can be obtained by replacing the variab…

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…

Matching Patterns with Variables under Hamming Distance

The Edit Distance to k-Subsequence Universality

Efficiently Testing Simon's Congruence

The Edit Distance to $k$ -Subsequence Universality