TERMGRAPH 2009 Preliminary Proceedings

PREFACE TERMGRAPH 2009 took place in York (UK) on March 22, 2009, as a one-day satellite event of ETAPS 2009. Previous editions of the TERMGRAPH workshops series took place in Barcelona (2002), in Rome (2004), in Vienna (2006), and in Braga (2007). The advantage of computing with graphs rather than terms (strings or trees) is that common subexpressions can be shared, which improves the efficiency of computations in space and time. Sharing is ubiquitous in implementations of programming languages: many implementations of functional, logic, object-oriented and concurrent calculi are based on term graphs. Term graphs are also used in symbolic computation systems and automated theorem proving. The aim of TERMGRAPH 2009 was to bring together researchers working in these different domains and to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in term graph rewriting. Topics of interest for the workshop are all aspects of term graphs and sharing of common subexpressions in rewriting, programming, automated reasoning and symbolic computation. This includes (but is not limited to) term rewriting, graph transformation, programming languages, models of computation, graph-based languages, semantics and implementation of programming languages, compiler construction, pattern recognition, databases, bioinformatics, and system descriptions. This report contains the eight contributions presented during the workshop: they were selected by the Program Committee according to originality, significance, and general interest. In addition to these presentations, the programme included two invited lectures by H\'el\`ene Kirchner and Fabio Gadducci.