The 0-1 law fails for frame satisfiability of propositional modal logic
Proceedings - Symposium on Logic in Computer Science - Trang 225-234
Tóm tắt
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.
Từ khóa
#Logic #Kernel #Vocabulary #Bars #Computational modeling #Computational complexity #Combinatorial mathematics #H infinity controlTài liệu tham khảo
10.1006/inco.1993.1062
10.1016/0012-365X(90)90373-P
10.1109/LICS.1998.705685
10.2307/421076
10.1007/978-1-4612-2822-6_10
10.1007/3-540-44612-5_6
erdo?s, 1960, On the evolution of random graphs, Pupl Math Inst Hungar Acad Sci, 7, 17
10.1016/0304-3975(94)00182-I
chva?tal, 1973, On the computational complexity of finding a kernel
10.1016/0890-5401(90)90065-P
10.1007/BF01071084
10.1016/0012-365X(90)90327-E
10.2307/2272945
fagin, 1974, Generalized first-order spectra and polynomial time recognizable sets, SIAM-AMS Proceedings, 7, 43
10.1016/0168-0072(94)90084-1
10.1007/s001530100135