Matching regular expressions on uncertain data = Búsqueda de patrones sobre datos con incertidumbre
Author
Gil Carvajal, ArturoAdvisor
Santini, SimoneEntity
UAM. Departamento de Ingeniería InformáticaDate
2018-06Subjects
infinite stream; uncertain data; regular expression; Informática; MatemáticasEsta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Internacional.
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.
Files in this item
Google Scholar:Gil Carvajal, Arturo
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as https://creativecommons.org/licenses/by-nc-nd/4.0/
Related items
Showing items related by title, author, creator and subject.
-
Log file regular expression pattern matching and capture with GPUs
Pinto Silva, Antonio Luis
2016-09 -
En búsqueda de la matriz holística ante los estados de certeza, riesgo, incertidumbre y caos
Arbó, Jorge O. P.
2017-04