A study of two graph rewriting formalisms: Interaction Nets and MONSTR
Richard Banach, George Angelos Papadopoulos · 1997
Two superficially similar graph rewriting formalisms, Interaction Nets and MONSTR, are studied. Interaction Nets come from multiplicative Linear Logic and feature undirected graph edges, while MONSTR arose from the desire to implement generalized term graph rewriting efficiently on a distributed architecture and utilizes directed graph arcs. Both formalisms feature rules with small left-hand sides consisting of two main graph nodes. A translation of Interaction Nets into MONSTR is described for both typed and untyped nets, while the impossibility of the opposite translation rests on the fact that net rewriting is always Church–Rosser while MONSTR rewriting is not. Some extensions to the net formalism suggested by the relationship with MONSTR are discussed, as well as some related implementation issues.