Chargement...

- Domaine
- Algorithmics-Graphs-Combinatorics
- Domain - extra
- Année
- 2010
- Starting
- 2010
- État
- Open
- Sujet
- Logic, 0-1 laws and definability
- Thesis advisor
- DE ROUGEMONT Michel
- Co-advisors
- Laboratory
- Collaborations
- 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
- 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

filename | créé | hits | filesize | ||
---|---|---|---|---|---|

Aucun fichier joint à cette fiche |

Nicole Bidoit

Stéphanie Druetta

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