Информационная система "Конференции"

Abstracts

Computability theory

We introduce a notion of random structures, in which relations are generated randomly using some standard probability distributions. We are investigating asymptotic behavior of monotone properties of random structures definable by formulas in existential fragment of first-order logic with equality. This fragment of first-order logic is commonly used in database theory. One of the most important characteristics of probabilistic behavior of monotone properties of random structures is their threshold functions. We show how one can compute the threshold functions for the properties expressible in this fragment. We also show that formulas from this fragment cannot express any property with a sharp threshold. Finally, we show that this fragment has a 0 - 1 law for a large class of probability functions.

Additional information:

korovin_voronkov.pdf (39 kb)

Mail to Webmaster alc9@math.nsc.ru

|Home Page| |English Part|

Go to Home