Domain

AlgorithmicsGraphsCombinatorics

Domain  extra


Year

2010

Starting

2010

Status

Open

Subject

Logic, 01 laws and definability

Thesis advisor

DE ROUGEMONT Michel

Coadvisors


Laboratory

EXT LIAFA

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 kgrams of structures. The techniques may generalize to other Logics and connect with approaches on approximate satisfiability.

Context

01 laws have been discovered in the 1980s for firstorder Logic.
Some of these laws generalize to other Logics and some don't.
In Finite Model theory, many other techniques such as EhrenfeuchtFraisse games, allow to prove non definability results, in complement to the 01 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

Details


Expected funding

Research contract

Status of funding

Expected

Candidates


user


Created 
Tuesday 02 of March, 2010 10:31:41 CET 
LastModif 
Tuesday 02 of March, 2010 16:19:45 CET 