Asymptotic Conditional Probability in Modal Logic: A Probabilistic Reconstruction of Nonmonotonic Logic

Riccardo Rosati, Georg Gottlob.
In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI 2005), pages 1378-1383, 2005. ISBN 0938075934.

Abstract:

We analyze the asymptotic conditional validity of modal formulas, i.e., the probability that a formula g is valid in the finite Kripke structures in which a given modal formula f is valid, when the size of these Kripke structures grows to infinity. We characterize the formulas g that are almost surely valid (i.e., with probability 1) in case f is a flat, S5-consistent formula, and show that these formulas g are exactly those which follow from f according to the nonmonotonic modal logic S5G. Our results provide -- for the first time -- a probabilistic semantics to a well-known nonmonotonic modal logic, establishing a new bridge between nonmonotonic and probabilistic reasoning, and give a computational account of the asymptotic conditional validity problem in Kripke structures.

Bibtex entry:

@String{IJCAI-05 = "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI~2005)"}

@Inproceedings{RoGo05,
author = "Riccardo Rosati and Georg Gottlob",
title = "Asymptotic Conditional Probability in Modal Logic: A Probabilistic Reconstruction of Nonmonotonic Logic",
booktitle = IJCAI-05,
pages = "1378--1383",
year = 2005,
isbn = "0938075934",
}