Logic in Computer Science (LICS 2002)

Paper: The 0-1 law fails for frame satisfiability of propositional modal logic (at LICS 2002)

Authors: Jean-Marie Le Bars

Abstract

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.

BibTeX

  @InProceedings{LeBars-The01lawfailsforfra,
    author = 	 {Jean-Marie Le Bars},
    title = 	 {The 0-1 law fails for frame satisfiability of propositional
    modal logic},
    booktitle =  {Proceedings of the Seventeenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2002},
    year =	 2002,
    editor =	 {Gordon Plotkin},
    month =	 {July}, 
    location =   {Copenhagen, Denmark}, 
    publisher =	 {IEEE Computer Society Press}
  }