Membership Problem with Adjacency Matrix

Yolanda Moyao Martinez, Darnes Vilariño Ayala, Jose de Jesus Lavalle Martínez, Carlos Guillen Galban


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 2 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.


Membership problem, hypergraph, adjacency matrix

Full Text: PDF (Spanish)