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
Détails
Expected funding
Research contract
Status of funding
Expected
Candidates
Utilisateur
Créé
Mardi 02 mars 2010 10:31:41 CET
dernière modif.
Mardi 02 mars 2010 16:19:45 CET
Fichiers joints
filename
créé
hits
filesize
Aucun fichier joint à cette fiche
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit Assistante
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 à lri.fr