-- 计算机科学 数据结构与算法 arXiv:2606.18878 (cs) [提交于 2026年6月17日] 题目：高效的间隙约束语言在复杂事件识别中的应用 作者：Antoine Amarilli，Florin Manea，Tina Ringleb，Markus L. Schmid 论文摘要：对于字符串 $u, D \text{ in } \boldsymbol{\text{Σ}}^*$，$u$ 在 $D$ 中的子序列嵌入是一个函数 $e : \{1, 2, \ldots, |u|\} \to \{1, 2, \ldots, |D|\}$，使得对于每个 $i \in \{1, 2, \ldots, |u|-1\}$，都有 $e(i) < e(i+1)$，且 $u$ 的第 $i$ 个符号等于 $D$ 的第 $e(i)$ 个符号。一个间隙约束 $(i, j, L)$ 是一个三元组，其中 $1 \leq i < j \leq |u|$，$L$ 是一个关于 $\boldsymbol{\text{Σ}}$ 的正则语言。嵌入 $e$ 满足间隙约束 $(i, j, L)$ 当且仅当 $D$ 中位于 $e(i)$ 和 $e(j)$ 之间的部分是来自 $L$ 的单词。我们研究了带有间隙约束的子序列匹配问题，这在复杂事件识别（CER）中具有重要意义：给定 $u, D \text{ in } \boldsymbol{\text{Σ}}^*$ 和一组间隙约束 $C$，找出一个在 $D$ 中满足所有约束的 $u$ 的嵌入。
通常，子序列匹配是 NP 完全的，已知的唯一可解决变种限制了间隙约束的区间结构。在本研究中，我们表明，只要间隙约束语言满足我们称之为左凸性（left-convexity）的一种性质，就可以相对高效（事实上，在 SETH 下是最优的）地解决带有任意区间结构的子序列匹配问题，时间复杂度为 $O(|D| (|u| + |C|))$。左凸语言足够表达有趣的现实场景，例如长度约束 $L = \{w \mid |w| \in [a, b]\}$，其中 $a, b \in \boldsymbol{\text{N}}$。
我们还展示了如何有效枚举所有满足条件的嵌入，这对于 CER 的潜在应用尤为相关。最后，我们指出非左凸语言可能导致不可解性，即如果除了长度约束外，允许 $\{aa, \}$ 作为唯一的非左凸约束语言，则问题再次变为 NP 完全。 评论：50 页 主题：数据结构与算法 (cs.DS) ; 数据库 (cs.DB); 正规语言与自动机理论 (cs.FL) 引用为：arXiv:2606.18878 [cs.DS] (或 arXiv:2606.18878v1 [cs.DS] 版本) https://doi.org/10.48550/arXiv.2606.18878
博主点评： 本文展示了如何通过左凸性性质有效解决复杂事件识别中的子序列匹配问题，提出的算法在实际应用中具有重要意义。对间隙约束语言的深入研究为相关领域提供了新思路，值得关注。