The 0-1 law fails for frame satisfiability of propositional modal logic

Le Bars Jean-Marie

To appear at Symposium on Logic in Computer Science (LICS'2002), Copenhagen, Denmark, July 22nd - 25th, 2002


The digraph property KERNEL is a very simple and well-known property studied in various areas. We previously defined a variant of this property as a counterexample of 0-1 law for the monadic existential second order logic with at most two first-order variables, over structures with 16 binary relations. Goranko and Kapron have defined a variant in frames which is also expressible in the fragment which expresses frame satisfiability of propositional modal logic, a small fragment of the logic above over structures with only one relation. We prove that this variant is almost surely false and we propose other variants of this property and establish that one of them provides a counterexample of the 0-1 law for frame satisfiability of propositional modal logic. This refutes a result by Halpern and Kapron which establishes that the 0-1 law holds for this logic. This also strongly refines our previous counterexample.

Server START Conference Manager
Update Time 15 Mar 2002 at 15:30:30
Start Conference Manager
Conference Systems