Logic and Combinatorics
23rd and 24th September
2006
Satellite Workshop
of the conference :
Computer Science
Logic 25th 29th
September 2006
Abstracts of
talks ; Slides
For all emails, replace DOT by
a dot.
Isolde
Adler (
Slides : http://www2.informatik.hu-berlin.de/~adler/publications.html
The hypertree-width of a hypergraph measures how close a hypergraph is
to being acyclic. Similar to tree-width, many problems that are NP-complete in
general, become tractable when restricted to instances whose underlying
hypergraph has bounded hypertree-width.
In analogy to tree-width, the hypertree-width of a hypergraph H can be characterised by the number of cops necessary to catch a robber
on the hypergraph.
In this game the robber's
escape space must decrease in a monotone way. In contrast to the robber and
cops game characterising tree-width, the number of cops necessary to win the
game may increase due to this restriction, but at most by a factor of three.
Achim
Blumensath (
A versatile method to generate
graphs with desirable properties consists in applying graph operations that
preserve these properties to a selected class of basic graphs.
In this talk we consider
graphs with a simple monadic theory. We will give an overview of common
operations that preserve decidability of monadic theories.
In particular, we will present
the generalised sums of Shelah and the Muchnik construction, which is one of
the most powerful decidability results in logic that, e.g., subsumes
Rabin’s Theorem.
Manuel
Bodirsky (
Slides : http://www.informatik.hu-berlin.de/~bodirsky/publications/tcsp.html
We introduce two new tractable
temporal constraint languages, which both strictly contain the Ord-Horn language
introduced by Bürkert and Nebel. We also prove that our languages are maximally tractable, i.e., if we add a new temporal relation to our
constraint languages, the corresponding constraint satisfaction problem becomes
NP-complete.
For that we apply the so-called product
Ramsey theorem, which we believe will be useful in similar contexts of
constraint satisfaction complexity classification.
Finally, we prove that the two
languages cannot be solved by Datalog, or, equivalently, by
local consistency techniques.
This talk is about joint work
with Jan Kara.
Thomas Colcombet (Rennes, France), colcombe@irisaDOTfr : Set interpretations.
Slides : http://www.labri.fr/perso/courcell/Logiquecombinatoire/SzegedColcombetSlides.pdf
Set interpretations are
logically defined mappings from structures to structures. As for standard
monadic (second order) interpretations, set interpretations are defined by a
collection of monadic second order
formulas describing the universe and the relations of the resulting structure
in terms of the original one. The
difference lies in the fact that the free variables of the formulas are monadic
(set) variables instead of first-order variables, and consequently, the
elements of the resulting structure are sets of
elements of the original one. In particular, such transformations map
structures having a decidable monadic second-order theory to structures having
a decidable first-order theory.
In this talk we study the
expressive power of set interpretations when applied to trees.
Bruno
Courcelle (
Certain equivalence classes of graphs or of other
combinatorial objects are characterized in terms of a common tree, the tree of
a hierarchical decomposition of a
certain kind.
Our main examples of such
situations are :
(1) 2-connected graphs with
the same cycle matroid,
(2) Planar drawings of a
planar connected graph,
(3) Transitive orientations of
a comparability graph,
(4) Pairs of linear orders
defining a dimension 2 partial order,
(5) Interval models of an
interval graph,
(6) Double occurrence words
representing a same circle graph,
(7) Plane connected graphs
having the same diagonal walks.
The trees correspond in all
these cases to the modular decomposition
(3,4,5), to Tutte’s decomposition of
a 2-connected graph in 3-connected components (1,2), to the “split” decomposition defined by
Cunningham (6), to the decomposition of a connected graph in 2-connected
components (7).
In all these cases the
relevant trees are canonical and
constructible from the considered graphs by Monadic Second-Order formulas. The
equivalence class can then be generated by Monadic Second-Order formulas from
any of its elements, and in some cases auxiliary linear orders.
The lecture will discuss the
case of circle graphs.
Arnaud
Durand and Frédéric Olive (Paris
and
We consider the problem of query evaluation for fragments of
first-order logic. We revisit the
complexity of these problems and exhibit a logical and combinatorial approach
that permits to obtain tractability results for various classes : in particular
for acyclic conjunctive queries and first-order queries on structures of
bounded degree and on trees. This method simply tries to eliminate (under
reasonable i.e. linear cost) variables of the formula while preserving the
result of the query.
Then, we consider query
problems as generation problems for
which the complexity measure is the
delay between two consecutive tuples of
the result, and we show some interesting consequences for the complexity
of these problems of the above described method.
Emeric
Gioan (
Slides : http://www.labri.fr/perso/courcell/Logiquecombinatoire/SzegedGioanSlides.pdf
First, I will review logical
structures that describe pseudo-line arrangements and present their
refinement into graph drawings.
A pseudo-line arrangement is a
finite set of curves in a plane, such
that each one is homeomorphic to a line, and two pseudo-lines always cross at
one point. The advantage of pseudo-lines in comparison with (straight) lines is
that there exist combinatorial axiomatizations : an equivalence with rank 3
oriented matroids and a first-order logical axiomatization given by B.
Courcelle and F. Olive.
Graph drawings whose edges are drawn with curves that cross at most once
are described with a similar but
extended logical structure by B. Courcelle. Then we will consider these
structures up to triangle flips.
Two pseudo-line arrangements in general positions can always be
transformed, one into the another by a
sequence of flips (this is Ringel's theorem).
We will see that, in a drawing
of a complete graph, the combinatorial map together with the set of
pairs of edges that cross determine the drawing up to a sequence of flips (this
is a generalization of Ringel's theorem).
Finally, some questions appear
in the characterization of such logical structures, and for building sequences
of flips transforming into one another two arrangements or two drawings when
some flips are forbidden. This situation occurs in the extension of these
structures to plane drawings of braids or spatial graphs encoded by rank 4
oriented matroids.
Petr
Hlineny (
Slides : http://www.labri.fr/perso/courcell/Logiquecombinatoire/SzegedHlinenySlides.pdf
We study the problem of
decidability of MSO theories on various
(restricted) matroid classes. When considering the matroids
representable over a finite field (which is in structural sense similar to
graphs embedded on a surface), the situation resembles ordinary graphs as
incidence structures. The monadic second-order
theory of all matroids over a finite field of bounded branch-width is
decidable [H]. Conversely, the decidability of monadic second-order theory of a class of matroids over a finite
field implies a bound on the
branch-widths of the matroids in this class
[HS].
The situation gets much more versatile and
interesting when considering matroids in general (as "abstract",
without a particular representation). We shall focus mainly on this part, and
present some particular observations and results, and mainly open questions and
directions for future research. This is related to another interesting question
already raised by [HS] :
What could be a
"good" width measure for general
matroids ?
[H] : P. Hlinený : Branch-width, parse trees, and monadic
second-order logic for matroids. J. of Combinatorial Theory, B, Vol. 96, 2006,
pp. 325-351.
[HS] P. Hlinený and D. Seese : Trees,
grids, and MSO decidability: From graphs to matroids. Theoretical Computer Science, Vol. 351, 2006,
pp. 372-393.
Florent
Madelaine (
Constraint
satisfaction problems (CSPs) can be modelled in terms of existence of
homomorphism between structures.
Feder and Vardi have
introduced a fragment of Monadic Second Order logic, called MMSNP, and proved that the class of problems
captured by MMSNP is computationally equivalent to the class of CSPs. However,
this computational equivalence involves a change of signature and a highly
non-trivial “derandomisation” due to Kun.
In fact, in terms of Descriptive Complexity, the picture is
quite different. There are problems in MMSNP that are not CSPs (over the same
signature). Moreover, in general, Bodirsky proved that problems captured by
MMSNP are actually (finite unions of) well behaved infinite Constraint Satisfaction Problems. This yields the
following question:
Given a sentence of MMSNP, can we decide whether it
captures a finite or an infinite CSP?
This question, when restricted
to the first-order fragment of MMSNP is related to the notion of homomorphism duality studied in Structural Combinatorics. Another
popular concept in this field is that of restricted
homomorphism duality, which corresponds in our setting to the following
question:
Given a sentence of MMSNP, can we decide whether it
captures a finite or an infinite CSP, when restricted to a class of input K ?
We will present an overview of results concerning MMSNP, CSP and duality.
Janos
Makowsky (
We present a surprising connection between certain totally categorical
structures and graph invariants.
Let CatStruct(t) be the class of totally
categorical t-structures. We define a functor M from Graphs to CatStruct(t) having the
following property.
Let p: Graphs à Z^(Z^k)
be a graph invariant which has positive values for non-negative inputs, tends
to infinity for inputs tending to
infinity, and is polynomially bounded.
Then, if p is representable in M(G), then p is a polynomial.
This allows us to show that many graph invariants are graph polynomials.
On the other hand, every graph polynomial definable in Second-Order logic is
representable in the above sense.
(Joint work with Boris Zilber,
Jerzy
Marcinkowski (
There are no good tools known for proving, for a given
sublogic of Monadic Second Order Logic (MSOL), that it is strictly
less expressive than the whole MSOL. Take for example the prefix subclasses
of MSOL. The simple case of the so called monadic NP, is quite well
understood. But if more second order quantification is allowed, and in
particular, if alternation between first and second order quantifiers is
allowed, then what we know is almost to nothing. It is
humiliating, but the question (from Ajtai, Fagin, Stockmeyer, 98), whether the,
so called, closed monadic NP, is closed under
complementation, appears to be well beyond our reach. The first
part of my talk will be a survey of results and problems in this
area.
Then I will concentrate on
another sublogic of MSOL, called Graph Logic. The second order quantification
is restricted here not in terms of the quantifier prefix, but by the way the
formula following a quantifier can be written: each use of a set quantifier
splits here the structure into two substructures -- this set and its
complementation -- and the substructures are invisible from each other. Does
this restriction really change anything ? This question which was studied by
some clever authors (and also in my CSL 06 paper), will be the topic of the
second part of my talk.
Luc
Segoufin (
We consider families of trees
definable in monadic second-order (MSO)
logic : they are regular tree languages.
Among MSO definable families of trees, we will give an effective characterization
of those that are definable in first-order (FO) logic, in the language of graphs. We will present a couple of
applications of this result and then
discuss an interesting conjecture that would allow to lift this result
to families of graphs of bounded tree-width.