• DocumentCode
    2195245
  • Title

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

  • Author

    Le Bars, Jean-Marie

  • Author_Institution
    GREYC, Caen Univ., France
  • fYear
    2002
  • fDate
    2002
  • Firstpage
    225
  • Lastpage
    234
  • Abstract
    The digraph property KERNEL is a very simple and wellknown 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 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.
  • Keywords
    computability; computational complexity; formal logic; temporal logic; KERNEL; computational complexity; digraph property; frame satisfiability; monadic existential second order logic; propositional modal logic; temporal logics; Bars; Combinatorial mathematics; Computational complexity; Computational modeling; H infinity control; Kernel; Logic; Vocabulary;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 2002. Proceedings. 17th Annual IEEE Symposium on
  • ISSN
    1043-6871
  • Print_ISBN
    0-7695-1483-9
  • Type

    conf

  • DOI
    10.1109/LICS.2002.1029831
  • Filename
    1029831