[ont.events] U of Toronto AI-Theory seminar, Nov. 28

clarke@csri.toronto.edu (Jim Clarke) (11/24/88)

      AI/THEORY SEMINAR - Monday, November 28, 11 a.m. in Room PA 105
                (PA = Pharmacy Building, 19 Russell Street)

                             Joseph Y. Halpern
                        IBM Almaden Research Centre

            "An Analysis of First-Order Logics of Probability"

   We consider two approaches to giving semantics to first-order logics
of probability.  The first approach puts a probability on the domain, and
is appropriate for giving semantics to formulas involving statistical in-
formation such as ``The probability that a (typical) bird flies is greater
than .9.'' The second approach puts a probability on possible worlds, and
is appropriate for giving semantics to formulas describing degrees of be-
lief, such as ``The probability that Tweety (a particular bird) flies is
greater than .9.''  The two approaches can be easily combined, allowing us
to reason in a straightforward way about statistical information and de-
grees of belief.  We then consider issues of decidability and expressive-
ness for the corresponding logics of probability.  It turns out that it
takes very little to make reasoning about probability highly undecidable.
For example, when the probability is on the domain, if the  language con-
tains only unary predicates then the validity problem is decidable.  Howev-
er, if the language contains even one binary predicate, the validity prob-
lem is even harder than the validity problem for full second order arith-
metic with set variables (technically, it is Pi2_1 complete).  This
means it is certainly not axiomatizable.  We do provide sound axiom systems
that we show are complete for interesting subcases (for example, in the
case that probability is on the domain and the language contains only unary
predicates).  This suggests that our axioms are powerful enough to enable
us to carry out a great deal of interesting reasoning about probability.
Finally, we show that, although the two approaches capture quite different
intuitions about probability, there is a precise sense in which they are
equi-expressive.

The results on decidability are joint with Martin Abadi.
-- 
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
              (416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu     CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke