ACO The ACO Seminar (2012-2013)

Oct 4, 3:30pm, Wean 8220
Simcha Haber, CMU
An extension of the Ehrenfeucht Fraisse game with random graphs applications

Abstract:

Consider a formal language L able to describe some properties of graphs, and a sequence of random graphs G(n). If for any L-property P, the probability that G(n) has P tends either to one or to zero, we say that the 0-1 law holds for (L,G(n)). Studying 0-1 laws serves to get a better understanding of the logic L and of the random graph G(n). The Ehrenfeucht Fraisse game is a model theoretic tool that is commonly used in this field when the logic under discussion is the first order logic. We will present an extension of this game and its relation to logics with Lindstrom quantifiers. We will then use the game to describe some new results and to give new proofs for known theorems.


Back to the ACO home page