14:00
18:00

In this thesis, we present efficient approximation algorithms for questions that arise from the study of formal languages. 
The first part considers problems related to approximate pattern matching, a task in which one must identify all substrings of a text that are similar to a given pattern. We study multiple notions of similarity, including similarity up to rotation, substitutions, and edits. We also study strings with wildcards, which model missing or corrupted data. 
The second part considers approximating membership in a formal language in three frameworks: property testing of regular languages, for which we fully characterize the complexity with a trichotomy result; computing the distance between a word and a formal language, for palindromes and squares; and computing the palindromic length of a word.
 

English
Amphi LaBRI