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-1law 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 two variants in frames which expresses frame satisfiability of propositional modal logic, also expressible in a small fragment of the logic above over structures with only one relation. We propose another variant of KERNEL which 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. It also strongly refines our previous counterexample.
Index Terms:
Modal and Temporal Logics, Finite Model Theory, Computational Complexity
Citation:
Jean-Marie Le Bars, "The 0-1 law fails for frame satisfiability of propositional modal logic," lics, pp.225, 17th Annual IEEE Symposium on Logic in Computer Science (LICS'02), 2002