etaps-logo etaps_logo-termgraph

TERMGRAPH 2009 Programme

Please register through the ETAPS 2009 site

TERMGRAPH 2009 [] is a one-day satellite event of ETAPS 2009, which will take place in York, UK, from March 22 to 29. Previous editions of the TERMGRAPH workshops series took place in Barcelona (2002), in Rome (2004), in Vienna (2006), and in Braga (2007).

Aims and scope top

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.

Research in term and graph rewriting ranges from theoretical questions to practical implementation issues. Many different research areas are included, for instance: the modelling of first- and higher-order term rewriting by (acyclic or cyclic) graph rewriting, the use of graphical frameworks such as interaction nets and sharing graphs to model strategies of evaluation (for instance, optimal reduction in the lambda calculus), rewrite calculi on cyclic higher-order term graphs for the semantics and analysis of functional programs, graph reduction implementations of programming languages, graphical calculi modelling concurrent and mobile computations, object-oriented systems, graphs as a model of biological or chemical abstract machines, and automated reasoning and symbolic computation systems working on shared structures.

The aim of this workshop is 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 top

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): 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.

Invited Speakerstop

Fabio Gadducci, Dipartimento di Informatica, Pisa, Italy.
Title: Some properties of an old-fashioned algebra for graphs

Hélène Kirchner, INRIA Bordeaux - Sud-Ouest Research Center, France.
Title: A Port Graph Calculus and its Application to Autonomic Computing, joint work with Oana Andrei.
abstract (PDF)

Accepted papers top

The following papers have been accepted for presentation at the Workshop:

  1. Bahareh Badban. A Term Rewriting technique for Decision Graphs
  2. Didier Buchs and Steve Hostettler. Σ Decisions Diagrams
  3. Maribel Fernández, Ian Mackie, Shinya Sato and Matthew Walker. Recursive Functions with Pattern-Matching in Interaction Nets
  4. Davide Grohmann and Marino Miculan. Graph Grammars for Local Bigraphs
  5. Abubakar Hassan, Ian Mackie and Shinya Sato. Compilation of interaction nets
  6. Ian Mackie, Miguel Vilaça and Jorge Sousa Pinto. Iterators, Recursors and Interaction Nets
  7. Frank Raiser and Thom Frühwirth. Strong Joinability Analysis for Graph Transformation Systems in CHR
  8. Ruben Viegas and Francisco Azevedo. Lazy constraint imposing for Improving the path constraint

The preliminary proceedings, including the listed papers, will be distributed at the workshop and will be accessible on-line as a Technical Report of the Dipartimento di Informatica di Pisa.

After the workshop, authors will be invited to submit a revised version of their presentation. Accepted contributions will appear in a issue of Elsevier's Electronic Notes in Theoretical Computer Science (ENTCS).

Important Dates top

(Extended) Submission Deadline: December 22, 2008
Notification (postponed): January 20, 2009
Pre-proceedings version due: February 6, 2009
Workshop: March 22, 2009
ETAPS Conference: March 22-29, 2009

Programme Committee top

Andrea Corradini Dipartimento di Informatica, Pisa, Italy [Chair]
Rachid Echahed CNRS, Laboratoire d'Informatique de Grenoble (LIG), France
Marko van Eekelen Radboud University of Nijemegen, The Netherlands
Maribel Fernández King's College London, UK
Ian Mackie École Polytechnique, France
Detlef Plump University of York, UK

Contact top

Andrea Corradini
Dipartimento di Informatica
Pisa, Italy

Valid HTML 4.01 Transitional