Melhorias nas Consultas de Caminhos em Gráfos: Expressão, Avaliação e Satisfiabilidade Mínima
linguages livres-de-contexto, consultas de caminhos em grafos, minimização de grafos.
Nós tratamos três problemas relacionados a grafos e linguagens livres-de-contexto: (1) nós desenvolvemos uma notação alternativa para expressar linguagens livres-de-contexto; (2) nós desenvolvemos e experimentamos um algoritmo para avaliação de consultas de caminhos livres-de-contexto; e (3) nós formalizamos o prolema da minimização de grafos restrita a uma linguagem formal, para o qual desenvolvemos soluções para os casos onde a linguagem formal é regular ou livre-de-contexto.