14 citations · 52 across the 22 of their papers we have counts for
6 papers · 1 filter
An SMT Solver for Regular Expressions and Linear Arithmetic over String Length
Murphy Berzish, Mitja Kulczynski, Federico Mora +4
We present a novel length-aware solving algorithm for the quantifier-free first-order theory over regex membership predicate and linear arithmetic over string length. We implement…
Blocksequences of k-local Words
Pamela Fleischmann, Lukas Haschke, Florin Manea +3
The locality of words is a relatively young structural complexity measure, introduced by Day et al. in 2017 in order to define classes of patterns with variables which can be match…
The Edit Distance to -Subsequence Universality
Pamela Fleischmann, Maria Kosche, Tore Koß +2
A word is a subsequence of another word if can be obtained from by deleting some of its letters. The word with alph is called -subsequence universal i…
Efficiently Testing Simon's Congruence
Pawel Gawrychowski, Maria Kosche, Tore Koss +2
Simon's congruence is defined as follows: two words are -equivalent if they have the same set of subsequences of length at most . We propose an algorithm which…
Scattered Factor-Universality of Words
Laura Barker, Pamela Fleischmann, Katharina Harwardt +2
A word is a scattered factor of a word if can be obtained from by deleting some of its letters: there exist the (potentially empty) words $v_0,v_1,..,v…
Reconstructing Words from Right-Bounded-Block Words
Pamela Fleischmann, Marie Lejeune, Florin Manea +2
A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of sca…