Improvements on graph path queries: expression, evaluation, and minimum-weight satisfiability - Medeiros, Ciro Morais (2022)
Nós tratamos três problemas relacionados a consultas de caminhos em grafos. A maioria das linguagens de consulta em grafos atuais suporta consultas de caminhos regulares. No entanto, algumas aplicações, como análise de código-fonte e genética, exigem consultas de caminhos livres-de-contexto. As consultas de caminhos livres-de-contexto usam linguagens livres-de-contexto. Não existe uma notação padrão para linguagens livres-de-contexto mais simples do que gramáticas livres-de-contexto. A avaliação de uma consulta de caminhos livres-de-contexto é mais complexa do que a de uma consulta de caminhos regulares. Além disso, em algumas aplicações, deseja-se ter o grafo mínimo que preserve as respostas para uma determinada consulta de caminhos. Para resolver cada um desses problemas, nós: (1) desenvolvemos uma notação alternativa para expressar linguagens livres-de-contexto; (2) projetamos, implementamos e experimentamos um algoritmo de avaliação de consulta de caminhos livres-de-contexto; e (3) formalizamos o problema da minimização de grafos restrita a uma linguagem formal, para o qual desenvolvemos soluções para os casos em que a linguagem formal é regular ou livre-de-contexto.