Problema de membresía con matriz de adyacencia

• Autores: Yolanda Moyao Martínez, José de Jesús Lavalle-Martínez, Carlos Guillén Galbán, Darnes Vilariño Ayala
• Localización: Computación y Sistemas (CyS), ISSN 1405-5546, ISSN-e 2007-9737, Vol. 25, Nº. 3, 2021, págs. 523-535
• Idioma: español
• DOI: 10.13053/cys-25-3-4023
• Títulos paralelos:
  • Membership Problem with Adjacency Matrix
• Enlaces
  • Texto completo
• Resumen
  • 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.

• Referencias bibliográficas
  • Aalbersberg, I.,Rozenberg, G.,Ehrenfeucht, A.. (1986). On the membership problem for regular dnlc grammars. Discrete Applied Mathematics....
  • Aguiñaga, S.,Chiang, D.,Weninger, T.. (2018). Learning hyperedge replacement grammars for graph generation. CoRR.
  • Chiang, D.,Andreas, J.,Bauer, D.,Hermann, K. M.,Jones, B.,Knight, K.. (2013). Parsing graphs with hyperedge replacement grammars. 51st Annual...
  • Courcelle, B.. (1991). The monadic second-order logic of graphs V: on closing the gap between definability and recognizability. Theor. Comput....
  • Drewes, F.,Kreowski, H.-J.,Habel, A.. (1997). Handbook of graph grammars and computing by graph transformation. World Scientific Publishing...
  • Engelfriet, J.. (1997). Handbook of formal languages. Springer-Verlag New York, Inc.. New York, NY, USA.
  • Gallo, G.,Scutellà, M.. (1998). Directed hypergraphs as a modelling paradigm. Decisions in Economics and Finance. 21. 97-123
  • Gilroy, S.,López, A.,Maneth, S.. (2017). Parsing graphs with regular graph grammars. 6th Joint Conference on Lexical and Computational Semantics...
  • Gottlob, G.,Grohe, M.,Musliu, N.,Samer, M.,Scarcello, F.. (2005). Graph-Theoretic Concepts in Computer Science. Springer Berlin Heidelberg....
  • Groschwitz, J.,Koller, A.,Teichmann, C.. (2015). Graph parsing with s-graph grammars. 53rd Annual Meeting of the Association for Computational...
  • Habel. (1991). Hyperedge Replacement: Grammars and Languages. 1. University of Bremen. United States of America.
  • Lange, K.-J.,Welzl, E.. (1987). String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing. Discrete Applied...
  • Lautemann, C.. (1990). The complexity of graph languages generated by hyperedge replacement. Acta Informatica. 27. 399-421
  • Minas, M.. (2000). Hypergraphs as a uniform diagram representation model. 6th International Workshop on Theory and Application of Graph Transformations,...
  • Peng, X.,Song, L.,Gildea, D.. (2015). A synchronous hyperedge replacement grammar based approach for AMR parsing. Nineteenth Conference on...
  • Peuser, C.. (2018). Software Technologies: Applications and Foundations - STAF 2018 Collocated Workshops. Springer. Toulouse, France.
  • Rozenberg, G.. (1997). Handbook of graph grammars and computing by graph transformation.
  • Rozenberg, G.,Welzl, E.. (1986). Boundary NLC graph grammars basic definitions, normal forms, and complexity. Information and Control. 69....