Tina Ringleb

collaborators

3 papers

cs.DS2026

Tractable Gap-Constraint Languages for Complex Event Recognition

Antoine Amarilli, Florin Manea, Tina Ringleb +1

For strings $u, D \in I^£^{*}$ , 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 \{…

cs.DS2026

Linear Time Subsequence and Supersequence Regex Matching

Antoine Amarilli, Bartlomiej Dudek, Florin Manea +2

It is well-known that checking whether a given string $w$ matches a given regular expression $r$ can be done in quadratic time $O (∣ w ∣ \cdot ∣ r ∣)$ and that this cannot be improved to…

cs.DS2025

Efficiently Finding All Minimal and Shortest Absent Subsequences in a String

Florin Manea, Tina Ringleb, Stefan Siemer +1

Given a string $w$ , another string $v$ is said to be a subsequence of $w$ if $v$ can be obtained from $w$ by removing some of its letters; on the other hand, $v$ is called an absen…