8 citations · 11 across the 9 of their papers we have counts for
12 papers
Jumbled Simon's Equivalence and Embeddings
Pamela Fleischmann, Annika Huch, Sungmin Kim +2
\emph{Jumbled scattered factors} are a generalisation of scattered factors (or subsequences) where a jumbled scattered factor is obtained from another word by deleting and rearrang…
Jumbled Scattered Factors
Pamela Fleischmann, Annika Huch, Melf Kammholz +1
In this work, we combine the research on (absent) scattered factors with the one of jumbled words. For instance, is an absent scattered factor of $\mathtt{cauliflow…
-Universality of Regular Languages Revisited
Duncan Adamson, Pamela Fleischmann, Annika Huch +2
A subsequence of a word is a word such that , for some set of indices . A word is \e…
Subsequence Matching and Analysis Problems for Formal Languages
Szilárd Zsolt Fazekas, Tore Koß, Florin Manea +2
In this paper, we study a series of algorithmic problems related to the subsequences occurring in the strings of a given language, under the assumption that this language is succin…
-Universality of Regular Languages
Duncan Adamson, Pamela Fleischmann, Annika Huch +3
A subsequence of a word is a word such that , for some set of indices . A word is…
Matching Patterns with Variables Under Simon's Congruence
Pamela Fleischmann, Sungmin Kim, Tore Koß +4
We introduce and investigate a series of matching problems for patterns with variables under Simon's congruence. Our results provide a thorough picture of these problems' computati…
Longest Common Subsequence with Gap Constraints
Duncan Adamson, Maria Kosche, Tore Koß +2
We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the d…
Combinatorial Algorithms for Subsequence Matching: A Survey
Maria Kosche, Tore Koß, Florin Manea +1
In this paper we provide an overview of a series of recent results regarding algorithms for searching for subsequences in words or for the analysis of the sets of subsequences occu…
Subsequences in Bounded Ranges: Matching and Analysis Problems
Maria Kosche, Tore Koß, Florin Manea +1
In this paper, we consider a variant of the classical algorithmic problem of checking whether a given word is a subsequence of another word . More precisely, we consider the…
Absent Subsequences in Words
Maria Kosche, Tore Koß, Florin Manea +1
An absent factor of a string is a string which does not occur as a contiguous substring (a.k.a. factor) inside . We extend this well-studied notion and define absent sub…
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…