17th Annual IEEE Symposium on Logic in Computer Science (LICS'02) The 0-1 law fails for frame satisfiability of propositional modal logic Copenhagen, Denmark July 22-July 25 ISBN: 0-7695-1483-9
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 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||