Revisiting Graph Types in HyperLMNtal: A Modeling Language for Hypergraph Rewriting

IEEE Access

Kazunori Ueda¹  Alimujiang Yasen² 

[1] Department of Computer Science and Engineering, Waseda University, Tokyo, Japan;School of Information Management, Xinjiang University of Finance and Economics, Urumqi, China;

关键词: Graph types;    hypergraphs;    hypergraph rewriting;    modeling languages;    unification;   

DOI  :  10.1109/ACCESS.2021.3112903

来源: DOAJ

【 摘 要 】

Hypergraphs are a highly expressive data structure for modeling and programming, for which high-level language constructs are yet to be established. HyperLMNtal is a modeling language based on hypergraph rewriting. Rewrite rules can copy and remove subgraphs identified by graph types which serve as a wildcard construct that enables powerful handling of subgraphs. HyperLMNtal has featured several graph types over the years, enabling it to encode various computational models. Important applications of graph types include the modeling of formal systems involving name binding including the $\lambda $ -calculus. However, the concept of graph types for hypergraphs has not been studied in sufficient detail, and our recent work revealed that the encoding of a unification algorithm modulo $\alpha $ -equivalence requires further evolution of graph types. This paper describes the motivation and redesign of a graph type for handling subgraphs appearing in the above applications and conduct experiments to show performance improvements. We believe that the idea of graph types could be useful in programming and modeling languages in general and is worth further investigation and deployment.

【 授权许可】

Unknown