Workshop on Logic, Graph Transformations and Discrete Structures,

a satellite event of the first International Conference on Graph Transformations (ICGT 2002 )

Where and when     Organisers    Program Committee   Objectives   Program   Intended audience Registration Open Problems

Date and location

The workshop will take place during the afternoon of October 11 , and during the morning and afternoon of October 12 , in Barcelona .

ICGT will take place from October 8 to October 11. Other satellite events will take place on October 7 and 8, and on October 11 and 12.


B. Courcelle , LaBRI (U. Bordeaux-1 ),
P. Weil , LaBRI (U. Bordeaux-1 and CNRS ),

Program Committee

B. Courcelle , LaBRI (U. Bordeaux-1 )
H. Ehrig , C.S. Department (T.U. Berlin )
P. Weil , LaBRI (U. Bordeaux-1 and CNRS )


The main objective of this workshop is to confront the competences developped within the graph transformation community with the intuitions of neighboring fields.

A list of relevant directions to explore is the following:

The workshop will consist of invited talks, and will reserve ample time for discussions.

Open Problems

A number of open problems were presented in the last session of the workshop. Some participants put their open problem on virtual paper :
Bruno Courcelle's open problem sheet

Intended audience

People interested in graph transformations, but also in logic on structures other than graphs, such as words, posets, event structures, etc. And more generally people interested in structural  properties of discrete or combinatorial structures.

This should be of interest for both experienced researchers and more junior colleagues, including PhD students, recent doctors and post-docs.

For further details: do not hesitate to contact the organisers.


see the conference's main page: ICGT 2002


FRIDAY October 11, 2002 

14:30 - 15:25    Janos Makowsky (Technion, Haïfa) : Graph polynomials and generating functions definable in Monadic Second Order Logic (extended abstract available on this link )

15:25 - 16:00     Alex Glikson (Technion, Haïfa) : Finite Model Theory characterization of some graph grammars

16:00 - 16:30    Coffee Break

16:30 - 17:15     Markus Frick (LFCS, Edinburgh) : The complexity of first order and monadic second order logic

17:15 - 18:00     Detlef Seese (AIFB, Karlsruhe) : Complexity and dynamic systems: tree-width, regularity and information flow

SATURDAY October 12, 2002

09:00 - 10:00     Pascal Weil (LaBRI, Bordeaux) : Partial orders, graph grammars and logic

10:00 - 10:30    Coffee Break

10:30 - 11:30     Anca Muscholl (LIAFA, Paris) : Specification and verification using Message Sequence Charts

11:30 - 12:30     Dietrich Kuske (University of Leicester) : Algebraic characterizations of first-order logic on posets

12:30 - 14:30     Lunch Break

14:30 - 15:30     Bruno Courcelle (LaBRI, Bordeaux) : On a conjecture by D. Seese (transparencies available on this link in PDF)

15:30 - 16:00    Kamal Lodaya (Institute of Mathematical Sciences, Chennai) : A definition of fusion for posets

16:00 - 16:30    Coffee Break

16:30 - 17:00    Harald Gropp (University Heidelberg) : Graph transformation from Llull to Brunel  CANCELLED

17:00 - 18:30    Open problems session

Pascal Weil     October 13, 2002