|
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.
|
![[Show/Hide Left Column]](styles/coelesce/img/icons/oleftcol.png "[Show/Hide Left Column]"){kind=icon}
