Title :
The 0-1 law fails for frame satisfiability of propositional modal logic
Author :
Le Bars, Jean-Marie
Author_Institution :
GREYC, Caen Univ., France
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;
Conference_Titel :
Logic in Computer Science, 2002. Proceedings. 17th Annual IEEE Symposium on
Print_ISBN :
0-7695-1483-9
DOI :
10.1109/LICS.2002.1029831