Markus L. Schmid

collaborators

3 papers

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.FL2026

A General Information Extraction Framework Based on Formal Languages

Markus L. Schmid

For a terminal alphabet $I^£$ and an attribute alphabet $I^$ , a $(I^£, I^)$ -extractor is a function that maps every string over $I^£$ to a table with a column per attribute and with s…

cs.DS2024

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration

Pawel Gawrychowski, Florin Manea, Markus L. Schmid

Information extraction from textual data, where the query is represented by a finite transducer and the task is to enumerate all results without repetition, and its extension to th…