3 citations · 9 across the 13 of their papers we have counts for
6 papers · 1 filter
A Generic Information Extraction System for String Constraints
Joel D. Day, Adrian Kröger, Mitja Kulczynski +3
String constraint solving, and the underlying theory of word equations, are highly interesting research topics both for practitioners and theoreticians working in the wide area of…
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…
Matching Patterns with Variables Under Edit Distance
Paweł Gawrychowski, Florin Manea, Stefan Siemer
A pattern is a string of variables and terminal letters. We say that matches a word , consisting only of terminal letters, if can be obtained by replacing the variab…
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…
Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems
Joel D. Day, Maria Kosche, Florin Manea +1
We consider subsequences with gap constraints, i.e., length-k subsequences p that can be embedded into a string w such that the induced gaps (i.e., the factors of w between the pos…
Formal Languages via Theories over Strings
Joel D. Day, Vijay Ganesh, Nathan Grewal +1
We investigate the properties of formal languages expressible in terms of formulas over quantifier-free theories of word equations, arithmetic over length constraints, and language…