{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiextk6fnqr2fbhxrbhy4f22xzbjpnc52hiy7sgd3bw2hahxkn47wu",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3moksknu5sah2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.18878v1",
  "publishedAt": "2026-06-18T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Antoine Amarilli",
    "Florin Manea",
    "Tina Ringleb",
    "Markus L. Schmid"
  ],
  "textContent": "**Authors:** Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid\n\nFor strings $u, D \\in Σ^*$, a subsequence embedding of $u$ in $D$ is a function $e \\colon \\\\{1, 2, \\ldots, |u|\\\\} \\to \\\\{1, 2, \\ldots, |D|\\\\}$ with $e(i) < e(i+1)$ for every $i \\in \\\\{1, 2, \\ldots, |u|-1\\\\}$ and the $i$-th symbol of $u$ equals the $e(i)$-th symbol of $D$. A gap-constraint for $u$ is a triple $(i, j, L)$ with $1 \\leq i < j \\leq |u|$ and $L$ is a regular language over $Σ$. An embedding $e$ satisfies a gap-constraint $(i, j, L)$ if the factor of $D$ strictly between positions $e(i)$ and $e(j)$ is a word from $L$. We investigate the subsequence matching problem with gap-constraints, which is relevant in the context of complex event recognition (CER): given $u, D \\in Σ^*$ and a set $C$ of gap-constraints, find an embedding of $u$ in $D$ that satisfies all gap-constraints from $C$. In general, subsequence matching is NP-complete and the only known tractable variants restrict the interval structure of the gap-constraints. In this work, we show that we can solve subsequence matching with gap-constraints with an arbitrary interval structure rather efficiently (in fact, optimally under SETH) in time $O(|D| (|u| + |C|))$ if the gap-constraint languages satisfy a property which we dub left-convexity: whenever $u v w \\in L$ and $v \\in L$, then also $uv \\in L$. Left-convex languages are sufficiently expressive to model interesting real-world scenarios considered in CER, e.g., length constraints $L = \\\\{w \\mid a \\leq |w| \\leq b\\\\}$ for $a, b \\in \\mathbb{N}$. We also show how our algorithm can be used in order to efficiently enumerate all satisfying embeddings, which is particularly relevant for possible applications in CER. Finally, we show how non-left-convex languages can lead to intractability, i.e., if in addition to length constraints we allow $\\\\{aa, ε\\\\}$ as the only non-left-convex constraint language, then the problem is NP-complete again.",
  "title": "Tractable Gap-Constraint Languages for Complex Event Recognition"
}