Improvements on Graph Path Queries: Expression, Evaluation, and Minimum-Weight Satisfiability
Soutenue par Ciro Morais Medeiros, co-tutelle entre le LIFO (Orléans) & Universidade federal do Rio Grande do Norte (Natal, Brésil) le 30/08/2022. Encadrée par Mírian Halfeld Ferrari Alves et Martin Musicante. Début de nombreux échanges enrichissants avec Mirian & le LiFO. Lien. [Présidence du jury]
We deal with three problems related to graph path queries. Most current graph query languages support regular path queries. However, some applications such as source-code analysis and genetics require context-free path queries. Context-free path queries use context-free languages. There is no standard notation for context-free languages simpler than context-free grammars. The evaluation of a context-free path query is more complex than a regular path query. Moreover, in some applications, it is desired to have the minimum graph that preserves answers to a given path query. To address each of those problems, we: (1) develop an alternative notation for expressing context-free languages;(2) design, implement and experiment with a context-free path query evaluation algorithm; and (3) formalize the formal-language-constrained graph minimization problem, for which we design solutions for the cases where the formal language is regular or context-free.