Resumen de Problema de membresía con matriz de adyacencia

Yolanda Moyao Martínez, José de Jesús Lavalle-Martínez, Carlos Guillén Galbán, Darnes Vilariño Ayala

• español

  Resumen: En este artículo se propone un algoritmo, para resolver el problema de membresía en Gramáticas de Reemplazo de Hiperaristas (HRG). Given a hypergraph H with labeled nodes and hyperedges, dirigidas y enraizadas, el problema consiste en determinar si H ∈ L(G), donde G ∈ HRG, es decir si H está en el lenguaje generado por G, para esto el análisis se lleva a cabo directamente en la Matriz de Adyacencias del hipergrafo H. Además, para el algoritmo propuesto se presenta la demostración de que es correcto.

• English

  Resumen: In this article, proposed a algorithm to solve the membership problem in Hyperedge Replacement Grammars (HRG). Given a hypergraph H with labeled nodes rooted and directed hyperedges, the problem consists in determining if H ∈ L(G), where G is in HRG, this is to say, if H is in the language generated by G, for this the analysis is done directly in the Adjacency Matrix of the hypergraph H. For the algorithm proposed, also presents the proof of its correctness.