Conference paper
Counterexample to theorems of Cox and Fine
Joseph Y. Halpern
aaai 1996
It is shown that a 0-1 law holds for propositional modal logic, both for structure validity and for frame validity. In the case of structure validity, the result follows easily from the well-known 0-1 law for first-order logic. However, the proof gives considerably more information. It leads to an elegant axiomatization for almost-sure structure validity, and sharper complexity bounds. Since frame validity can be reduced to a II11 formula, the 0-1 law for frame validity helps delineate when 0-1 laws exist for second-order logics.
Joseph Y. Halpern
aaai 1996
Joseph Y. Halpern
aaai 1993
Joseph Y. Halpern, Yoram Moses, et al.
PODC 1990
Ronald Fagin, Yoram Moses, et al.
aaai 1994