The workshop will be held in Room 0C2 at 175, rue du Chevaleret 75013
Paris, France. See the following
link for directions.
Point (Équipe de Logique Mathématique, FNRS) and Jean-Eric
Pin (LIAFA, CNRS)
|9:30 - 10:30||Nicole Schweikardt||Approximation Schemes for First-Order 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 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.)
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 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.
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
Lv and query language Lq, we say that a
rewriting language Lr is complete for
Lq -to- Lv rewritings if every Q
in Lq can be rewritten in terms of V in
Lv using a query in Lr, 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.