BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Florin Manea (Georg-August Universität Göttingen)
DTSTART:20260408T130000Z
DTEND:20260408T140000Z
DTSTAMP:20260423T021240Z
UID:FLAT/19
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/19/">Op
 timal enumeration of regular pattern matches</a>\nby Florin Manea (Georg-A
 ugust Universität Göttingen) as part of One FLAT World Seminar\n\n\nAbst
 ract\nEnumerating all matches of a regular expression with capture variabl
 es (variable regex\, for short) to a document is a fundamental task in tex
 tual information extraction\, e.g.\, in connection to document spanners. S
 tate-of-the-art results [Amarilli et al.\, ACM TODS 2021] show how the mat
 ches of a variable regex\, representable by a sequential variable-set auto
 maton\, to a document can be enumerated with delay constant in the size of
  the document and polynomial in the size of the query\, after a preprocess
 ing requiring time linear in the size of the document and polynomial in th
 e size of the query.\n\nWe consider here the matching problem for regular 
 expressions with capture variables which can be represented as regular pat
 terns: $w_0x_0 w_1x_1 \\cdots w_{k}x_k w_{k+1}$\, where\, for $i\\in \\{0\
 ,\\ldots\,k+1\\}$\, $w_i$ is a string of terminal letters and\, for $i\\in
  \\{0\,\\ldots\,k\\}$\, $x_i$ is a variable. This problem naturally lies i
 n the intersection of information extraction and stringology\, as it can a
 lso be seen as computing all the ways in which $k+1$ given strings $w_0\,\
 \ldots\,w_{k+1}$ occur\, in this order and without overlaps\, in a given t
 ext $T$. We provide an optimal enumeration algorithm for this problem.\nAf
 ter a preprocessing requiring linear time in the size of the document $T$ 
 and the size of the query pattern $\\alpha$\, we can enumerate all matches
  with worst-case constant delay (in combined complexity\, i.e.\, both in t
 he document- and the query-size).\n\nBased on: Paweł Gawrychowski\, Flori
 n Manea\, Stefan Siemer\, Paul Sarnighausen-Cahn.\n“Optimal Enumeration 
 of Regular Pattern Matches\,”\nto appear in PODS 2026.\n
LOCATION:https://researchseminars.org/talk/FLAT/19/
END:VEVENT
END:VCALENDAR