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

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 <inline-formula> <tex-math notation="LaTeX">$\lambda $ </tex-math></inline-formula>-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 <inline-formula> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula>-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.

Abstract licence: CC BY-NC-ND

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.