Tractable Gap-Constraint Languages for Complex Event Recognition

Antoine Amarilli, Florin Manea, Tina Ringleb +1

For strings $u,D\in {\Sigma }^{\ast }$, a subsequence embedding of $u$ in $D$ is a function $e:\{1,2,\dots ,|u|\}\to \{1,2,\dots ,|D|\}$ with $e(i)<e(i+1)$ for every $i \in \{1,2,…