ICGT 2004

The next International Conference on Graph Transformations will be organized in Roma from September 29 th until October 1^st, 2004.
Like in Barcelona in 2002, satellite workshops will be organized.
This is to announce a satellite workshop on

Logic and its applications to graphs, graph transformations and graph algorithms

that will be held on Friday MORNING and Saturday 1-2 October, 2004.

The main topic of the workshop is the use of logic for representing graph properties and graph transformations, and its relationships with combinatorics and complexity.
"Graph" is actually a generic and convenient wording, covering hypergraphs, relational structures, and related combinatorial structures, like matroids and linearly ordered graphs.

More precisely, the preliminary list of subjects of talks is the following :

1. Descriptions of combinatorial objects by relational structures ; hierarchical descriptions and related algorithms ; Expressive powers of fragments of logical languages like first-order logic, monadic second-order logic, mu-calculus and related languages for expressing properties and transformations of relational structures. Unequivalences of languages proved by Ehrenfeucht-Fraïssé games and other tools.
2. Graph transformations and construction of graph classes with decidable decision problems for logical languages related to monadic second-order logic. Structure of classes of graphs, hypergraphs and matroids having decidable monadic theories.
3. Descriptions of infinite structures by finite tools like finite or push-down automata, equation systems, logical formulas, logically described transformations from fundamental structures like trees. Related decidability results.
4. Infinite games on graphs and trees, their relations with finite automata and related logical languages ; winning strategies and their applications to program synthesis and to verification proofs of interactive programs and systems.
5. Applications to higher-level recursive program schemes and their related graphs and trees.
6. Efficient algorithms based on logical descriptions and hierchical structures. Descriptive complexity and applications to databases. Graph classes defined by forbidden configurations. Comparisons between complexity measures like branch-with, tree-width, clique-width and related notions.
7. Other topics related to logical descriptions of discrete structures.

This list is not exhaustive.

The workshop will be partially supported by the European network GAMES, coordinated by E. Graedel (Aachen, Germany).

The program committee consists of B. Courcelle and D. Janin (Labri, Bordeaux, France), H. Ehrig (Berlin, Germany), E. Graedel (Aachen, Germany).

However, the meeting will be organized as a workshop and not as a formal conference with proceedings prepared three months in advance.
Relevant documents (extended abstracts, full papers, slides) will be made available through the Web page of the workshop.

A problem session will be scheduled, together with informal presentations of ongoing research. Student papers will be wellcome in these informal sessions.

Registration fees and accomodation

The schedule is constrained by the organization of ICGT :
Friday October 1st from 9h to 13h, and Saturday 2nd from 9h to 18h, with breaks of course.

Registration fees will be of 100 euros for participation only to the workshop To be paid before end July ;
they are reduced to 50 euros for registered participants to ICGT conference.
They cover the participation to the workshop, the reproduction of documents (copies of the abstracts, documentation about Roma), three coffee breaks, and the lunch on Saturday.

Registration, accomodation, public transportation, payment of registration fees will be handled by the organization of  ICGT conference.

Contact : Bruno Courcelle , courcell@labri.fr , David Janin, janin@labri.fr

http://www.labri.fr/ ~courcell/LogicIcgt.html

General organization of ICGT and the satellite workshops :

F. Parisi-Presicce : parisi@dsi.uniroma1.it

http://icgt2004.dsi.uniroma1.it/

 July 4th, 2004
B. Courcelle