Matching regular expressions on uncertain data = Búsqueda de patrones sobre datos con incertidumbre

Abstract

The present work examines an extension of regular expressions to the case in which the string data is uncertain. In the standard embodiment of regular expressions, the input is a sequence of well positioned and well defined symbols from a finite alphabet Σ , and the output is an indication of whether the string matches the expression, that is, whether the string belongs to the language generated by the expression. In this work, we will assume uncertainty on the received input of the regular expressions. We will propose an uncertainty model based on receiving symbols corrupted by the noise of the channel over which they are emitted. As a consequence of this channel noise, during the process of symbol recognition, we won't just see a symbol, but a probability distribution υ : Σ --> [0, 1], where υ (a(n)) gives the probability that the symbol we are observing is a(n). Then, these symbols a(n), are submitted to the regular expression matching algorithm which operates over them. In this work, we shall develop algorithms to find the most likely match of a regular expressions ø based on the observations υ . In addition, we shall further extend the method to consider infinite streams of uncertain data, and we shall study their properties. Then, we will set and explore concrete practical examples, which could be extrapolated to similar scenarios, where we will apply our model and we will show that our algorithms ensure the decidability with probability 1 under determinate circumstances, can calculate justifiably the matching probability of a string of symbols, and are able to recover from reading errors.