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 JeanEric
Pin (LIAFA, CNRS)

9:00  Reception  
9:30  10:30  Nicole Schweikardt  Approximation Schemes for FirstOrder Definable Optimisation Problems 
10:30  11:00  Coffee break  
11:00  12:00  Anuj Dawar  Preservation properties in classes of finite structures 
12:00  14:00  Lunch break  
14:00  15:00  Richard Elwes  Asymptotic Classes and Measurable Structures 
15:10  16:10  Victor Vianu  Views and Queries: determinacy vs. rewriting 
16:20  17:30  Coffee and Buffet 

Let φ(X) be a firstorder 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 wellknown optimisation problems are firstorder 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 firstorder 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.)

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.

We consider classes of finite firstorder 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.

We investigate the question of whether a query Q can be answered
using a set V of views. We first define the problem in
informationtheoretic 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
informationtheoretic 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.