loading...
The 0-1 law fails for frame satisfiability of propositional modal logic
Copenhagen, Denmark July 22-July 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2002.102983117th Annual IEEE Symposium on Logic i ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Jean-Marie Le Bars, University of Caen
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.