Asymptotic conditional probabilities for firstorder 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 firstorder sentences. Given firstorder 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 01 laws that considers the limiting probability of firstorder 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 firstorder logic." Proceedings of the 24th ACM Symposium on Theory of Computing (STOC) (pp. 294305).


Bibtex citation
@inproceedings{Grove+al:STOC92,
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 firstorder logic",
pages = "294305",
year = "1992",
}
full list
