BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We consider a series of natural problems related to the proces
 sing of textual data\, rooted in areas as diverse as information extraction
 \, bioinformatics\, algorithmic learning theory\, or formal verification\, 
 and see how they can all be formalized within the same framework. In this f
 ramework\, we say that a pattern $\alpha$ (that is\, a string of string-var
 iables and letters from a fixed alphabet $\Sigma$) matches another pattern 
 $\beta$ if a text $T$\, over $\Sigma$\, can be obtained both from $\alpha$ 
 and $\beta$ by uniformly replacing the variables of the two patterns by wor
 ds over $\Sigma$. In the case when $\beta$ contains no variables\, i.e.\, $
 \beta=T$ is a text\, a match occurs if $\beta$ can be obtained from $\alpha
 $ by uniformly replacing the variables of $\alpha$ by words over $\Sigma$. 
 The respective matching problems\, i. e.\, deciding whether two given patte
 rns match or a pattern and a text match\, are computationally hard\, but ef
 ficient algorithms exist for classes of patterns with restricted structure.
  In this talk\, we overview a series of recent results in this area. 
DTSTAMP:20211207T223800
DTSTART:20211213T141500
CLASS:PUBLIC
LOCATION:Online via Zoom.
SEQUENCE:0
SUMMARY:Florin Manea (Universität Göttingen): Combinatorial String Solving
UID:107919904@/www.mi.fu-berlin.de
URL:https://www.mi.fu-berlin.de/en/facetsofcomplexity/monday/20211213-L-Man
 ea.html
END:VEVENT
END:VCALENDAR