-- Computer Science Data Structures and Algorithms arXiv:2606.18878 (cs) [Submitted on 17 Jun 2026] Title: Efficient Gap-Constraint Languages for Complex Event Recognition Authors: Antoine Amarilli, Florin Manea, Tina Ringleb, Markus L. Schmid Abstract: For strings $u, D \text{ in } \boldsymbol{\text{Σ}}^*$, a subsequence embedding of $u$ in $D$ is a function $e : \{1, 2, \ldots, |u|\} \to \{1, 2, \ldots, |D|\}$, such that for every $i \in \{1, 2, \ldots, |u|-1\}$, it holds that $e(i) < e(i+1)$ and the $i$-th symbol of $u$ equals the $e(i)$-th symbol of $D$. A gap-constraint $(i, j, L)$ is a triple where $1 \leq i < j \leq |u|$, and $L$ is a regular language over $\boldsymbol{\text{Σ}}$. 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 \text{ in } \boldsymbol{\text{Σ}}^*$ 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 efficiently (in fact, optimally under SETH) solve subsequence matching with gap-constraints with arbitrary interval structure in time $O(|D| (|u| + |C|))$ if the gap-constraint languages satisfy a property 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 |w| \in [a, b]\}$ for $a, b \in \boldsymbol{\text{N}}$. We also show how our algorithm can be used 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. Comments: 50 pages Subjects: Data Structures and Algorithms (cs.DS); Databases (cs.DB); Formal Languages and Automata Theory (cs.FL) Cite as: arXiv:2606.18878 [cs.DS] (or arXiv:2606.18878v1 [cs.DS] for this version) https://doi.org/10.48550/arXiv.2606.18878
Blogger's Review: This paper demonstrates the effective resolution of the subsequence matching problem in complex event recognition through left-convex properties. The proposed algorithm has significant implications for practical applications, and the in-depth study of gap-constraint languages offers new insights for the related fields, making it a noteworthy contribution.