Output-Linear enumeration for extensions of MSO
| dc.catalogador | yvc | |
| dc.contributor.advisor | Riveros Jaeger, Cristian | |
| dc.contributor.author | Muñoz Cruces, Martín Alonso | |
| dc.contributor.other | Pontificia Universidad Católica de Chile. Escuela de Ingeniería | |
| dc.date.accessioned | 2025-04-21T15:45:05Z | |
| dc.date.available | 2025-04-21T15:45:05Z | |
| dc.date.issued | 2025 | |
| dc.description | Tesis (Doctor in Engineering Sciences)--Pontificia Universidad Católica de Chile, 2025 | |
| dc.description.abstract | Enumeration algorithms for data extraction queries are especially relevant in modern day systems where data reaches extremely large sizes while sometimes having little-to-no organization. This thesis proposes an enumeration framework for queries for data extraction that can be modeled by different formal languages, and in some cases, over compressed data. This is done by the development of an enumeration data structure called Enumerable Compact Set, which provides a set of basic operations over sets, each implementable in constant time, that render a concise representation of the set of results which can then be enumerated efficiently. First, this thesis provides an algorithm for enumerating results of a query that has been modeled by a nested-word automata, over a nested document. This algorithm is built to work in a streaming setting, and requires time that is independent from the data size (constant in data-complexity) per input symbol. Second, we detail three algorithms for enumeration for queries that are modeled by contextfree grammars. We deal with the cases of unambiguous, rigid and determinable grammars, which require cubic, quadratic and linear time over the data, respectively. Third, we show enumeration over compressed documents via an algorithm that receives a regular-language query and a document that is concisely represented as a straight-line program. The enumeration can be done after linear time preprocessing in the size of thecompact representation. This thesis also serves as a proof of concept of the Annotated Automata model. This model properly subsumes Document Spanners efficient reductions, and allows the construction of algorithms that we deem to be more intuitive and easier to implement. Needless to say, all of our results are also applicable to Document Spanners. | |
| dc.description.abstract | Los algoritmos de enumeración para consultas de extracción de datos son especialmente relevantes en los sistemas de hoy en día, donde los datos alcanzan tamanos extremadamente grandes y, a veces, tienen poca o ninguna organización. Esta tesis propone un marco teórico de enumeración para consultas de extracción de datos que se pueden modelar mediante diferentes lenguajes formales y, en algunos casos, sobre datos comprimidos. Esto se hace mediante el desarrollo de una estructura de datos de enumeración llamada Enumerable Compact Sets (Conjuntos Comprimidos Enumerables en inglés), que proporciona un conjunto de operaciones basicas sobre conjuntos, cada uno implementable en tiempo constante, cuyo resultado es una representacion concisa del conjunto de resultados que luego se puede enumerar de manera eficiente. En el primer capítulo, esta tesis entrega un algoritmo para enumerar los resultados de una consulta que ha sido modelada por un automata de palabras anidadas, sobre un documento anidado. Este algoritmo esta diseñado para funcionar en un entorno de streaming y requiere un tiempo independiente al tamaño de los datos (constante en data complexity) en cada símbolo de entrada. En el segundo capítulo, detallamos tres algoritmos de enumeración para consultas que se modelan mediante gramáticas libres de contexto. Tratamos los casos de gramáticas no-ambiguas, rígidas y deterministas, que requieren tiempo cubico, cuadrático y lineal sobre los datos, respectivamente. En el tercer capítulo, mostramos la enumeración sobre documentos comprimidos mediante un algoritmo que recibe una consulta en lenguaje regular y un documento que se representaconcisamente como un programa straight-line. La enumeración se puede realizar después del preprocesamiento en tiempo lineal en el tamaño de la representación compacta. Esta tesis también sirve como prueba de concepto del modelo de Annotated Automata (Automatas anotados en inglés). Este modelo considera satisfactoriamente reducciones eficientes desde Document Spanners y permite la construcción de algoritmos que consideramos mas intuitivos y fáciles de implementar. Vale decir que todos nuestros resultados tambien son aplicables a Document Spanners. | |
| dc.fechaingreso.objetodigital | 2025-04-21 | |
| dc.format.extent | xi; 194 páginas | |
| dc.fuente.origen | SRIA | |
| dc.identifier.uri | https://repositorio.uc.cl/handle/11534/103355 | |
| dc.information.autoruc | Escuela de Ingeniería; Muñoz Cruces, Martín Alonso; S/I; 204015 | |
| dc.information.autoruc | Escuela de Ingeniería; Riveros Jaeger, Cristian; 0000-0003-0832-116X; 131276 | |
| dc.language.iso | en | |
| dc.nota.acceso | contenido completo | |
| dc.rights | acceso abierto | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Formal Languages and Automata Theory | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Estructuras de datos y algoritmos | |
| dc.subject | Lenguajes formales y teoría de autómatas | |
| dc.subject | Lógica en ciencias de la computación | |
| dc.subject.ddc | 620 | |
| dc.title | Output-Linear enumeration for extensions of MSO | |
| dc.type | tesis doctoral | |
| sipa.codpersvinculados | 204015 | |
| sipa.codpersvinculados | 131276 |