Logic and  Combinatorics

 

23rd  and 24th  September  2006

Szeged, Hungary

 

Satellite  Workshop  of the conference :

Computer Science Logic  25th 29th September 2006

 

Main page

 

Abstracts  of  talks ; Slides

 

 

For all emails, replace DOT by a dot.

 

Isolde Adler (Berlin, Germany), Adler@informatik.hu-berlinDOTde : Hyper-tree-width and related invariants (for a longer abstract).

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 (Darmstadt, Germany), blumensath@mathematik.tu-darmstadtDOTde : Graph operations and decidable monadic theories.

 

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 (Berlin, Germany, bodirsky@informatik.hu-berlinDOTde : The Complexity of Temporal Constraint Satisfaction, and the Product  Ramsey Theorem.

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 (Bordeaux, France) courcell@labriDOTfr : Graph equivalences and decompositions definable in Monadic Second-Order logic ; the case of Circle Graphs. (15 pages).

 

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 Marseille, France), durand@logique.jussieuDOTfr, Frederic.Olive@cmi.univ-mrsDOTfr : Query problems on unary functions, quantifier elimination and enumeration.

 

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 (Montpellier, France), Emeric.Gioan@lirmmDOTfr : Logical axiomatizations of pseudo-line arrangements and of graph drawings with edge crossings.

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 (Brno, Czech Republic), petr.hlineny@vsbDOTcz : On monadic second-order theories of matroids

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 (Durham, Great Britain), f.r.madelaine@durham.acDOTuk : Constraint Satisfaction, structure homomorphisms and fragments of Second-Order logic

 

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 (Haïfa, Israel), janos@cs.technion.acDOTil : Graph polynomials and totally categorical structures

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, Oxford)

 

Jerzy Marcinkowski (Wroclaw, Poland), jma@swiatowit.ii.uni.wrocDOTpl : Some Monadic Games. With Combinatorics and Without.

 

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 (Paris, France), Luc.Segoufin@inriaDOTfr :  Monadic second-order properties that are first-order expressible on certain structures.

 

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.