Springe direkt zu Inhalt

Lecture by Florin Manea (Universität Göttingen): Combinatorial String Solving

Dec 13, 2021 | 02:15 PM

We consider a series of natural problems related to the processing 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 framework, we say that a pattern $\alpha$ (that is, a string of string-variables 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 words 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 patterns match or a pattern and a text match, are computationally hard, but efficient algorithms exist for classes of patterns with restricted structure. In this talk, we overview a series of recent results in this area.

Time & Location

Dec 13, 2021 | 02:15 PM

Online via Zoom.

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)