Abstract
Modal logics see a wide variety of applications in artificial intelligence, e.g. in reasoning about knowledge, belief, uncertainty, agency, defaults, and relevance. From the perspective of applications, the attractivity of modal logics stems from a combination of expressive power and comparatively low computational complexity. Compared to the classical treatment of modal logics with relational semantics, the use of modal logics in AI has two characteristic traits: Firstly, a large and growing variety of logics is used, adapted to the concrete situation at hand, and secondly, these logics are often non-normal. Here, we present a shallow model construction that witnesses PSPACE bounds for a broad class of mostly non-normal modal logics. Our approach is uniform and generic: we present general criteria that uniformly apply to and are easily checked in large numbers of examples. Thus, we not only re-prove known complexity bounds for a wide variety of structurally different logics and obtain previously unknown PSPACE-bounds, e.g. for Elgesem’s logic of agency, but also lay the foundations upon which the complexity of newly emerging logics can be determined.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Chellas, B.: Modal Logic. Cambridge Univ. Press, Cambridge (1980)
Cholvy, L., Garion, C., Saurel, C.: Ability in a multi-agent context: A model in the situation calculus. In: Toni, F., Torroni, P. (eds.) CLIMA 2005. LNCS (LNAI), vol. 3900, pp. 23–36. Springer, Heidelberg (2006)
D’Agostino, G., Visser, A.: Finality regained: A coalgebraic study of Scott-sets and multisets. Arch. Math. Logic 41, 267–298 (2002)
Demri, S., Lugiez, D.: Presburger modal logic is only PSPACE -complete. In: Furbach, U., Shankar, N. (eds.) IJCAR 2006. LNCS (LNAI), vol. 4130, pp. 541–556. Springer, Heidelberg (2006)
Elgesem, D.: The modal logic of agency. Nordic J. Philos. Logic 2, 1–46 (1997)
Fagin, R., Halpern, J.Y.: Reasoning about knowledge and probability. J. ACM 41, 340–367 (1994)
Fine, K.: In so many possible worlds. Notre Dame J. Formal Logic 13, 516–520 (1972)
Halpern, J.: The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic. Artificial Intelligence 75, 361–372 (1995)
Halpern, J., Pucella, R.: Reasoning about expectation. In: Uncertainty in Artificial Intelligence, UAI 2002, pp. 207–215. Morgan Kaufmann, San Francisco (2002)
Halpern, J.Y., Moses, Y.O.: A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence 54, 319–379 (1992)
Jones, A., Parent, X.: Conventional signalling acts and conversation. In: Dignum, F.P.M. (ed.) ACL 2003. LNCS (LNAI), vol. 2922, pp. 1–17. Springer, Heidelberg (2004)
Ladner, R.: The computational complexity of provability in systems of modal propositional logic. SIAM J. Comput. 6, 467–480 (1977)
Lewis, D.: Intensional logics without iterative axioms. J. Philos. Logic 3, 457–466 (1975)
Olivetti, N., Pozzato, G.L., Schwind, C.: A sequent calculus and a theorem prover for standard conditional logics. ACM Trans. Comput. Logic 8 (2007)
Papadimitriou, C.: On the complexity of integer programming. J. ACM 28, 765–768 (1981)
Pattinson, D.: Coalgebraic modal logic: Soundness, completeness and decidability of local consequence. Theoret. Comput. Sci. 309, 177–193 (2003)
Pauly, M.: A modal logic for coalitional power in games. J. Log. Comput. 12, 149–166 (2002)
Schröder, L.: A finite model construction for coalgebraic modal logic. J. Log. Algebr. Prog. 73, 97–110 (2007)
Schröder, L., Pattinson, D.: PSPACE reasoning for rank-1 modal logics. In: Logic in Computer Science, LICS 2006, pp. 231–240. IEEE, Los Alamitos (2006)
Tobies, S.: PSPACE reasoning for graded modal logics. J. Log. Comput. 11, 85–106 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schröder, L., Pattinson, D. (2008). Shallow Models for Non-iterative Modal Logics. In: Dengel, A.R., Berns, K., Breuel, T.M., Bomarius, F., Roth-Berghofer, T.R. (eds) KI 2008: Advances in Artificial Intelligence. KI 2008. Lecture Notes in Computer Science(), vol 5243. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85845-4_40
Download citation
DOI: https://doi.org/10.1007/978-3-540-85845-4_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85844-7
Online ISBN: 978-3-540-85845-4
eBook Packages: Computer ScienceComputer Science (R0)