Logic and  Combinatorics

 

23rd  and 24th  September  2006

Szeged, Hungary

 

Satellite  Workshop  of the conference :

Computer Science Logic  25th 29th September 2006

 

See  below the  program

 

The annual conference Computer Science Logic is sponsored by the European Association for Computer Science Logic. The conference is intended for computer scientists whose research activities involve logic, as well as for logicians working on issues significant for Computer Science.

 

A workshop on Applications of Combinatorics to Logic and of Logic to Combinatorics has been organized just before the conference Computer Science Logic.

 

Proposed topics were :

 

1)      Proof complexity

2)      Complexity of constraint satisfaction problems and other logically based problems.

3)      Logical expression of graph properties, graph decompositions, graph transformations and related notions.

4)      Logical expression of properties of matroids, isotropic systems, graph drawings and knots.

5)      Counting and enumeration problems.

6)      Polynomials associated with graphs and other combinatorial structures.

7)      Ramsey-type arguments applied to 0/1 laws and Ehrenfeucht-Fraïssé  games.

8)      "Countable" model theory.

 

 

This workshop was intended to people who work in logic (proof theory, finite model theory) on the one hand, and in combinatorics (graph theory, counting problems, algebraic notions associated with graphs and discrete structures) on the other. Recent results show how fruitful it is to associate graph theory, algebraic notions and monadic second-order logic.

 

List  of  speakers  and  lectures

Abstracts , emails of authors and slides of the presentations

 

 

Isolde Adler (Berlin) : Hyper-tree-width and related invariants

 

Achim Blumensath (Darmstadt) : Graph operations and decidable monadic theories.

 

Manuel Bodirsky (Berlin) : The Complexity of Temporal Constraint Satisfaction, and the Product  Ramsey Theorem.

 

Thomas Colcombet (Rennes) : Finite sets interpretations.

 

Bruno Courcelle (Bordeaux) : Graph equivalences and decompositions definable in monadic second-order logic ; the case of circle graphs.

 

Arnaud Durand and Frédéric Olive (Paris and Marseille) : Query problems on unary functions, quantifier elimination and enumeration.

 

Emeric Gioan (Montpellier) : Logical axiomatizations of pseudo-line arrangements and of graph drawings with edge crossings.

 

Petr Hlineny (Brno) : On monadic second-order theories of matroids

 

Florent Madelaine (Durham) : Constraint Satisfaction, graph homomorphism problems and fragments of Monadic Second order logic

 

Janos Makowsky (Haïfa) : Graph polynomials and totally categorical structures.

 

Jerzy Marcinkowski (Wroclaw) : Some Monadic Games. With Combinatorics and Without.

 

Luc Segoufin (Paris) :  Monadic second-order properties that are first-order expressible on certain structures.

 

           

 

            The organizer of CSL 2006  was  Zoltan Esik : ze@inf.u-szeged.hu

http://www.inf.u-szeged.hu/~csl06/