Computing with Terms and Graphs
9th International Workshop, April 8, 2016, Eindhoven


Part of ETAPS 2016

Background top

Research in term and graph rewriting ranges from theoretical questions to practical issues. Computing with graphs handles the sharing of common subexpressions in a natural and seamless way, and improves the efficiency of computations in space and time. Sharing is ubiquitous in several research areas, for instance: the modelling of first- and higher-order term rewriting by (acyclic or cyclic) graph rewriting, the modelling of biological or chemical abstract machines, the implementation techniques of programming languages: many implementations of functional, logic, object-oriented, concurrent and mobile calculi are based on term graphs. Term graphs are also used in automated theorem proving and symbolic computation systems working on shared structures. The aim of this workshop is to bring together researchers working in different domains on term and graph transformation 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.

Previous editions of the workshop took place in Barcelona (2002), Rome (2004), Vienna (2006), Braga (2007), York (2009), Saarbruecken (2011), Rome (2013) and Vienna (2014). The permanent TERMGRAPH site has further information.

Topics of Interesttop

Topics of interest include 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):

  • theory of first-order and higher-order term graph rewriting
  • infinitary and rational term/graph rewriting
  • graph rewriting in lambda calculus (sharing graphs, optimality)
  • term/graph based models of computation
  • term/graph rewriting tools: case studies and system descriptions
  • term/graph rewriting based aspects of:
    • semantics and implementation of programming languages
    • compiler construction
    • interaction nets and proof nets
    • pattern recognition
    • bioinformatics

Invited Speakerstop

Jörg Endrullis Vrije Universiteit Amsterdam, The Netherlands
Barbara König Duisburg Essen Universität, Germany


9:00-10:00 Barbara Koenig Termination of Graph and Term Graph Rewriting
10:00-10:30 (coffee break)
10:30-11:00 Georg Moser and Maria A Schett Kruskal's Tree Theorem for Term Graphs
11:00-11:30 Johannes Waldmann On the Construction of Matchbound Certificates
11:30-12:00 Detlef Plump Reasoning about Graph Programs
12:00-14:00 (lunch break)
14:00-15:00 Joerg Endrullis Non-Termination of Cycle Rewriting by Finite Automata
15:00-15:30 (coffee break)
15:30-16:00 Ian Mackie and Shinya Sato In-place Graph Rewriting with Interaction Nets
16:00-16:30 Anton Salikhmetov A token-passing net implementation of optimal reduction with embedded read-back
16:30-17:00 Ian Mackie Compiling Process Networks to Interaction Nets

Programme Committee top

Andrea Corradini [co-chair] Dipartimento di Informatica, Pisa, Italy
Maribel Fernández King's College London, UK
Ian Mackie École Polytechnique, France
Detlef Plump University of York, UK
Femke van Raamsdonk Vrije Universtiteit Amsterdam, The Netherlands
Hans Zantema [co-chair] Eindhoven University of Technology, The Netherlands

Call for Papers top

Extended abstracts of at most 5 pages can be submitted. This may include both original work and tutorials on any of the above mentioned topics; also unfinished work is welcome.
The page limit for submissions in both categories is 5 pages in EPTCS style.
Submissions should be submitted electronically in PDF via the EasyChair submission site, no later than February 15, 2016 (extended deadline).
Papers will be judged on relevance, originality, correctness, and usefulness.
The informal proceedings of TERMGRAPH 2016 will be included on the Etaps USB flash drive.
Extended versions of accepted papers get will be collected in EPTCS proceedings after an extra reviewing round after the workshop.

Important Dates top

Deadline for submission: February 15, 2016 (extended deadline)
Notification February 22, 2016
Final version March 7, 2016

Contact top

Andrea Corradini email: andrea@di.unipi.it
Hans Zantema email: h.zantema@tue.nl