My home page
My group
Professional activities

Daphne Koller Publications

Asymptotic conditional probabilities for first-order logic (1992)

by A. J. Grove, J. Y. Halpern, and D. Koller

Abstract: Motivated by problems that arise in computing degrees of belief}, we consider the problem of computing asymptotic conditional probabilities for first-order sentences. Given first-order sentences phi and theta, we consider the structures with domain {1,...,N} that satisfy theta, and compute the fraction of them in which phi is true. We then consider what happens to this fraction as N gets large. This is closely connected to the work on 0-1 laws that considers the limiting probability of first-order formulas, except that now we are considering asymptotic conditional probabilities. Although work has been done on special cases of asymptotic conditional probabilities, no general theory has been developed. This is probably due in part to the fact that it has been known that, if there is a binary predicate symbol in the vocabulary, asymptotic conditional probabilities do not always exist. We show that in this general case, almost all the questions one might want to ask (such as deciding whether the asymptotic probability exists) are highly undecidable. On the other hand, we show that the situation with unary predicates only is much better. If the vocabulary consists only of unary predicate and constant symbols, it is decidable whether the limit exists, and if it does, there is an effective algorithm for computing it. The complexity depends on two parameters: whether there is a fixed finite vocabulary or an infinite one, and whether there is a bound on the depth of quantifier nesting.

Download Information

A. J. Grove, J. Y. Halpern, and D. Koller (1992). "Asymptotic conditional probabilities for first-order logic." Proceedings of the 24th ACM Symposium on Theory of Computing (STOC) (pp. 294-305). pdf ps.gz

Bibtex citation

  author =       "A.~J. Grove and J.~Y. Halpern and D. Koller",
  booktitle =    {Proceedings of the 24th ACM Symposium on Theory of
                   Computing (STOC)},
  title =        "Asymptotic conditional probabilities for first-order logic",
  pages =        "294--305",
  year =         "1992",

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal