Journal: | Computación y sistemas |
Database: | |
System number: | 000560607 |
ISSN: | 1405-5546 |
Authors: | Moyao Martínez, Yolanda1 Lavalle Martínez, José de Jesús1 Guillén Galbán, Carlos1 Vilariño Ayala, Darnes1 |
Institutions: | 1Benemérita Universidad Autónoma de Puebla, Facultad de Ciencias de la Computación, México |
Year: | 2021 |
Season: | Jul-Sep |
Volumen: | 25 |
Number: | 3 |
Pages: | 523-535 |
Country: | México |
Language: | Español |
Spanish abstract | 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 abstract | 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. |
Keyword: | Problema de membresía, Hipergrafo, Matriz de adyacencias |
Keyword: | Membership problem, Hypergraph, Adjacency matrix |
Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |