Abstract
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 possible alternative parameters, namely diamond dimension and modal width. We show fixed-parameter tractability results using these measures where the exponential dependence on the parameters is much milder (doubly and singly exponential respectively) than in the case of modality depth thus leading to FPT algorithms for modal satisfiability with much more reasonable running times. We also give lower bound arguments which prove that our algorithms cannot be improved significantly unless the Exponential Time Hypothesis fails.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blackburn, P., van Benthem, J.F.A.K., Wolter, F.: Handbook of Modal Logic. Studies in Logic and Practical Reasoning, vol. 3. Elsevier Science Inc., New York (2006)
Chagrov, A.V., Rybakov, M.N.: How Many Variables Does One Need to Prove PSPACE-hardness of Modal Logics. In: Balbiani, P., Suzuki, N.-Y., Wolter, F., Zakharyaschev, M. (eds.) Advances in Modal Logic, pp. 71–82. King’s College Publications (2002)
Courcelle, B.: The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf. Comput. 85(1), 12–75 (1990)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Springer, Heidelberg (1999)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Reasoning About Knowledge. The MIT Press, Cambridge (1995)
Flum, J., Grohe, M.: Parameterized complexity theory. Springer, New York (2006)
Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1-3), 3–31 (2004)
Grohe, M.: Logic, graphs, and algorithms. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 14(091) (2007)
Halpern, J.Y.: The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic. Artif. Intell. 75(2), 361–372 (1995)
Halpern, J.Y., Moses, Y.: A guide to completeness and complexity for modal logics of knowledge and belief. Artif. Intell. 54(3), 319–379 (1992)
Ladner, R.E.: The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6(3), 467–480 (1977)
Nguyen, L.A.: On the complexity of fragments of modal logics. Advances in Modal Logic 5, 249–268 (2005)
Woeginger, G.: Exact algorithms for NP-hard problems: A survey. Combinatorial Optimization–Eureka, You Shrink!, 185–207
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Achilleos, A., Lampis, M., Mitsou, V. (2010). Parameterized Modal Satisfiability. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds) Automata, Languages and Programming. ICALP 2010. Lecture Notes in Computer Science, vol 6199. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14162-1_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-14162-1_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14161-4
Online ISBN: 978-3-642-14162-1
eBook Packages: Computer ScienceComputer Science (R0)