patternMinor
complexity of modal logic axioms
Viewed 0 times
axiomsmodalcomplexitylogic
Problem
I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper.
At the moment I have the following:
K- no restrictions on the frame, NPComplete
T- reflexive, NPComplete
K4- transitive, PSpaceComplete
S4 and S4.3 also PSpaceComplete
S5- symmetric, transitive and reflexive, NPComplete.
I am not able to find any results regarding complexity of the following axioms for modal logic:
D- serial
KB- symmetric
B- reflexive, symmetric
The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.
At the moment I have the following:
K- no restrictions on the frame, NPComplete
T- reflexive, NPComplete
K4- transitive, PSpaceComplete
S4 and S4.3 also PSpaceComplete
S5- symmetric, transitive and reflexive, NPComplete.
I am not able to find any results regarding complexity of the following axioms for modal logic:
D- serial
KB- symmetric
B- reflexive, symmetric
The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.
Solution
You might find interesting some of the results in On the Complexity of Fragments of Modal Logics by Linh Anh Nguyen (in Advances in Modal Logic, 2004: 249-268). A version of the paper is available in the home page of Nyugen.
And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.
And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.
Context
StackExchange Computer Science Q#52806, answer score: 3
Revisions (0)
No revisions yet.