[Show/Hide Left Column]

Sujets Help

View Item

Domain Algorithmics-Graphs-Combinatorics
Domain - extra
Year 2010
Starting 2010
Status Open
Subject Logic, 0-1 laws and definability
Thesis advisor DE ROUGEMONT Michel
Laboratory EXT LIAFA
Abstract For a logical sentence F, consider the density of structures which satisfy F, i.e. the number of structures of size n which satisfy F, normalized by the total number of structures of size n. This function of n may have a limit when n grows to infinity.
For first order logic on relational structures, this limit is 0 or 1.
We study the situation for more generalized Logics, and have to frame the problem differently.
In a recent paper (Kolaitis STOC 2009), this situation has been generalized to Logics with counting, using k-grams of structures. The techniques may generalize to other Logics and connect with approaches on approximate satisfiability.

Context 0-1 laws have been discovered in the 1980s for first-order Logic.
Some of these laws generalize to other Logics and some don't.
In Finite Model theory, many other techniques such as Ehrenfeucht-Fraisse games, allow to prove non definability results, in complement to the 0-1 laws.

There is a strong connection with techniques on approximate satisfiability, Property testing, and approximate algorithms with the new Kolaitis results, as in both cases the same sketches of finite structures are used.

It is expected that these new techniques will bring new lights both for Logic, Complexity and Algorithms.
Objectives The main objective is to combine Logics and combinatorics, as a way to understand the expressivity of various Logics.
Another objective is to understand how sketches of structures may be good approximations for the satisfiability and truth.

Work program 1. Read the Kolaitis 2009 paper and understand the approximate techniques based on Gowers Norm.
2. Combine this approach with the work on approximate satisfiability (LRI Complexity group),
3. Find the right framework for Logics with parity, counting and other generalized quantifiers.
Extra information
Prerequisite Master Research in Math or Theoretical Computer Science
Expected funding Research contract
Status of funding Expected
Created Tuesday 02 of March, 2010 10:31:41 CET
LastModif Tuesday 02 of March, 2010 16:19:45 CET

Ecole Doctorale Informatique Paris-Sud

Nicole Bidoit
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps

ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info at lri.fr