10 Aprile 2017
sala seminari - U14
AVVISO DI SEMINARIO
Lunedì 10 aprile 2017
alle ore 11:30
Nella Sala Seminari del DISCo
Dr. Florin Manea
Department of Computer Science, Kiel University
terrà un seminario dal titolo
Matching Patterns with Variables
A pattern (i.e., a string of variables and terminals) maps to a word, if this is obtained by uniformly replacing the variables by non-empty terminal words; deciding this is NP-complete in general. We present efficient algorithms that solve this problem for several restricted classes of patterns and discuss connections to other related problems. Finally, we discuss how solving efficiently the pattern matching problem for restricted patterns is connected to the complexity of deciding the satisfiability of word equations with sides fulfilling the respective restrictions.
Il seminario è aperto a tutti gli interessati.
Per informazioni: Raffaella Rizzi firstname.lastname@example.org
In archivio dal: 11/04/2017