A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

Details A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics

2009-05-19

arxiv.org/abs/0905.3108v1

Computer Science

Logic in Computer Science

Full proofs for paper presented at the IEEE Conference on Logic in Computer Science, 2009

Scientific paper

Graded modal logic is the formal language obtained from ordinary (propositional) modal logic by endowing its modal operators with cardinality constraints. Under the familiar possible-worlds semantics, these augmented modal operators receive interpretations such as "It is true at no fewer than 15 accessible worlds that...", or "It is true at no more than 2 accessible worlds that...". We investigate the complexity of satisfiability for this language over some familiar classes of frames. This problem is more challenging than its ordinary modal logic counterpart--especially in the case of transitive frames, where graded modal logic lacks the tree-model property. We obtain tight complexity bounds for the problem of determining the satisfiability of a given graded modal logic formula over the classes of frames characterized by any combination of reflexivity, seriality, symmetry, transitivity and the Euclidean property.

Affiliated with

Also associated with

No associations

Rating

A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-699953