First announcement

The workshop will be held in Room 0C2 at 175, rue du Chevaleret 75013 Paris, France. See the following link for directions.

Françoise Point (Équipe de Logique Mathématique, FNRS) and Jean-Eric Pin (LIAFA, CNRS)

Schedule

Nicole Schweikardt (Humboldt-University Berlin)

Let φ(X) be a first-order formula in the language of graphs that has a free set variable X, and assume that X only occurs positively in φ(X). Then a natural minimisation problem associated with φ(X) is to find, in a given graph G, a vertex set S of minimum size such that G satisfies φ(S). Similarly, if X only occurs negatively in φ(X), then φ(X) defines a maximisation problem. Many well-known optimisation problems are first-order definable in this sense, for example, MINIMUM DOMINATING SET or MAXIMUM INDEPENDENT SET. We prove that for each class C of graphs with excluded minors, in particular for each class of planar graphs, the restriction of a first-order definable optimisation problem to the class C has a polynomial time approximation scheme. A crucial building block of the proof of this approximability result is a version of Gaifman's locality theorem for formulas positive in a set variable. This result may be of independent interest. (This is joint work with Anuj Dawar, Martin Grohe, and Stephan Kreutzer.)

Anuj Dawar (University of Cambridge)

Among classical theorems of model theory, preservation theorems are results that relate the syntactic form of formulas to semantic closure properties of the structures they define. The status of preservation theorems in the finite has been an active area of research in finite model theory. More recent work in the area has shifted the focus from the class of all finite structures to classes of structures satisfying natural structural restrictions. In this talk I will examine various such results relating to preservation under homomorphisms, extensions and bisimulations.

Richard Elwes (University of Leeds)

We consider classes of finite first-order structures in which the definable sets have good asymptotic behaviour as the structures become large. An important example is the class of finite fields. We consider related infinite structures which admit a finitary counting measure on the definable sets (for example pseudofinite fields, and the random graph). We show that the machinery of "simplicity theory" comes into play. We shall consider various examples, give some geometric results, and discuss open questions.

Victor Vianu (U.C. San Diego)

We investigate the question of whether a query Q can be answered using a set V of views. We first define the problem in information-theoretic terms: we say that V determines Q if V provides enough information to uniquely determine the answer to Q. Next, we look at the problem of rewriting Q in terms of V using a specific language. Given a view language L_v and query language L_q, we say that a rewriting language L_r is complete for L_q -to- L_v rewritings if every Q in L_q can be rewritten in terms of V in L_v using a query in L_r, whenever V determines Q. While query rewriting using views has been extensively investigated for some specific languages, the connection to the information-theoretic notion of determinacy, and the question of completeness of a rewriting language, have received little attention. In this talk we investigate systematically the notion of determinacy and its connection to rewriting.