My home page
My group
Professional activities

Daphne Koller Publications

Asymptotic conditional probabilities: The non-unary case (1996)

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 extends the work on 0-1 laws that considers the limiting probability of first-order sentences, by considering asymptotic conditional probabilities. As shown in [Liogonkii,GHK1a], in the general case, asymptotic conditional probabilities do not always exist, and most questions relating to this issue are highly undecidable. These results, however, all depend on the assumption that theta can use a nonunary predicate symbol. Liogonkii shows that if we condition on formulas theta involving unary predicate symbols only (but no equality or constant symbols), then the asymptotic conditional probability does exist and can be effectively computed. This is the case even if we place no corresponding restrictions on phi. We extend this result here to the case where theta involves equality and constants. We show that the complexity of computing the limit depends on various factors, such as the depth of quantifier nesting, or whether the vocabulary is finite or infinite. We completely characterize the complexity of the problem in the different cases, and show related results for the associated approximation problem.

Download Information

A.J. Grove, J.Y. Halpern, and D. Koller (1996). "Asymptotic conditional probabilities: The non-unary case." Journal of Symbolic Logic, 61(1), 250-276. Full version of paper in STOC '92. pdf ps.gz

Bibtex citation

  title = {Asymptotic conditional probabilities: The non-unary case},
  author = {A.J. Grove and J.Y. Halpern and D. Koller},
  journal = {Journal of Symbolic Logic}, 
  volume = 61,
  number = 1, 
  month = {March},
  year = 1996, 
  pages = {250--276},
  note = {Full version of paper in STOC '92},

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