First announcement

Workshop on Finite Models

Monday, the 27th of March 2006

Organised by the Équipe de Logique Mathématique and the LIAFA

with the support of the Fédération de recherche en mathématiques de Paris centre


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)


 9:00  Reception 
 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

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 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.

Valid HTML 4.01!
Last modification 03/09/2006