Florin Manea(University of Göttingen)
hosted by seminar series Certified Verification with Applications
"Matching Patterns with Variables: A General Framework for Text Processing"
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 /α/ (that is, a string of string-variables and letters from a fixed alphabet /Σ/) matches another pattern /β/ if a text /T/, over /Σ/, can be obtained both from /α/ and /β/ by uniformly replacing the variables of the two patterns by words over /Σ/.
In the case when /β/ contains no variables, i.e., /β/ = /T/ is a text, a match occurs if /β/ can be obtained from /α/ by uniformly replacing the variables of /α/ by words over /Σ/.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.
Bio: Florin Manea obtained his PhD, Summa cum Laude, from the University of Bucharest, Romania, in 2007, with a thesis in the area of formal languages.He moved to Germany in 2009, at the University of Magdeburg, with a Humboldt fellowship, where he continued his work in the area of automata and formal languages.Between 2011 and 2019, Florin Manea worked at the University of Kiel, on his own DFG grants, in the area of combinatorics and algorithms on string.Since 2019, he is a Professor at the University of Göttingen, leading the research group on Fundamentals in Computers Science.His main research interests are String Algorithms and Combinatorics, String Solving, Efficient Algorithms and Data Structures, Automata Theory and Formal Languages, Computability and Complexity Theory, and Logic in Computer Science.
|Time:||Thursday, 09.12.2021, 13:00|