Term Graph Representations for Cyclic Lambda-Terms

Clemens Grabmayer
(Department of Philosophy, Utrecht University, The Netherlands)
Jan Rochel
(Department of Computing Sciences, Utrecht University, The Netherlands)

We study various representations for cyclic lambda-terms as higher-order or as first-order term graphs. We focus on the relation between 'lambda-higher-order term graphs' (lambda-ho-term-graphs), which are first-order term graphs endowed with a well-behaved scope function, and their representations as 'lambda-term-graphs', which are plain first-order term graphs with scope-delimiter vertices that meet certain scoping requirements. Specifically we tackle the question: Which class of first-order term graphs admits a faithful embedding of lambda-ho-term-graphs in the sense that (i) the homomorphism-based sharing-order on lambda-ho-term-graphs is preserved and reflected, and (ii) the image of the embedding corresponds closely to a natural class (of lambda-term-graphs) that is closed under homomorphism?

We systematically examine whether a number of classes of lambda-term-graphs have this property, and we find a particular class of lambda-term-graphs that satisfies this criterion. Term graphs of this class are built from application, abstraction, variable, and scope-delimiter vertices, and have the characteristic feature that the latter two kinds of vertices have back-links to the corresponding abstraction.

This result puts a handle on the concept of subterm sharing for higher-order term graphs, both theoretically and algorithmically: We obtain an easily implementable method for obtaining the maximally shared form of lambda-ho-term-graphs. Furthermore, we open up the possibility to pull back properties from first-order term graphs to lambda-ho-term-graphs, properties such as the complete lattice structure of bisimulation equivalence classes with respect to the sharing order.

In Rachid Echahed and Detlef Plump: Proceedings 7th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2013), Rome, 23th March 2013, Electronic Proceedings in Theoretical Computer Science 110, pp. 56–73.
Published: 25th February 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.110.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org