Computer Science – Logic in Computer Science
Scientific paper
2009-12-25
Computer Science
Logic in Computer Science
Scientific paper
We investigate the parameterized computational complexity of the satisfiability problem for modal logic and attempt to pinpoint relevant structural parameters which cause the problem's combinatorial explosion, beyond the number of propositional variables v. To this end we study the modality depth, a natural measure which has appeared in the literature, and show that, even though modal satisfiability parameterized by v and the modality depth is FPT, the running time's dependence on the parameters is a tower of exponentials (unless P=NP). To overcome this limitation we propose several possible alternative parameters, namely diamond dimension, box dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times.
Achilleos Antonis
Lampis Michael
Mitsou Valia
No associations
LandOfFree
Parameterized Modal Satisfiability 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 Parameterized Modal Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parameterized Modal Satisfiability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-269551