2 papers
cs.DS2024
Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
Florin Manea, Jonas Richardsen, Markus L. Schmid
For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap co…
cs.FL2022
Extending Shinohara's Algorithm for Computing Descriptive (Angluin-Style) Patterns to Subsequence Patterns
Markus L. Schmid
The introduction of pattern languages in the seminal work [Angluin, ``Finding Patterns Common to a Set of Strings'', JCSS 1980] has revived the classical model of inductive inferen…