Musicante, Martin AlejandroMedeiros, Ciro Morais2022-12-082022-12-082022-08-30MEDEIROS, Ciro Morais. Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability. Orientador: Martin Alejandro Musicante. 2022. 99f. Tese (Doutorado em Ciência da Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2022.https://repositorio.ufrn.br/handle/123456789/50056We 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.Acesso AbertoComputaçãoContext-free languagesGraph path queriesGraph minimizationdoctoralThesisCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO