Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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. ; 2024-02-19