Logic and Combinatorics
23rd and 24th September
2006
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 (
Achim
Blumensath (
Manuel
Bodirsky (
Thomas Colcombet (Rennes) : Finite sets interpretations.
Bruno
Courcelle (
Arnaud
Durand and Frédéric Olive (Paris
and Marseille) : Query problems on unary functions, quantifier elimination and
enumeration.
Emeric
Gioan (
Petr
Hlineny (
Florent
Madelaine (
Janos
Makowsky (Haïfa) : Graph polynomials and totally categorical structures.
Jerzy
Marcinkowski (
Luc
Segoufin (
The organizer of CSL 2006 was Zoltan Esik : ze@inf.u-szeged.hu
http://www.inf.u-szeged.hu/~csl06/