Matching Patterns with Variables in Approximate Settings
Dissertation
Datum der mündl. Prüfung:2024-01-31
Erschienen:2024-02-12
Betreuer:Prof. Dr. Florin Manea
Gutachter:Prof. Dr. Florin Manea
Gutachter:Prof. Dr. Carsten Damm
Gutachter:Prof. Dr. Sebastian Maneth
Dateien
Name:onlineAbgabe.pdf
Size:1.04Mb
Format:PDF
Zusammenfassung
Englisch
In the literature dealing with patterns with variables, a word, also called string, is a sequence of terminal letters, while a pattern is a sequence of terminal and variable letters. The problem of deciding if there is a substitution for all the variables in a pattern, such that a target word is obtained, is the matching problem for patterns with variables. In many problems related to the processing of textual data, it is essential to model uncertainty in the text, such as, e.g., typos in handwritten texts or mutations in biological data. For this reason, I introduce and present in this thesis our proposals of several settings which model uncertainty in the context of matching patterns with variables and a series of algorithmic and complexity theoretic results developed in these settings. The first setting, approached in Chapter 3, is concerned with matching patterns with variables under Hamming distance, that is, deciding if there is a substitution for all variables in a pattern, such that a word is obtained that is not "too far" from the target word with respect to the Hamming distance. The same problem is analyzed in Chapter 4 for the Edit distance and in Chapter 5 for a similarity measure based on k-Simon's congruence. The final problem in Chapter 6 is concerned with the edit distance of a word to a k-universal word, i.e., a word which contains all possible words of length k as subsequences.
Keywords: Pattern with variables; Matching algorithms; Hamming distance; Conditional lower bounds; Edit distance; Simon's congruence; Subsequences; k-subsequence universality