by Lutz Schröder and Dirk Pattinson
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.
Reference:
Lutz Schröder and Dirk Pattinson: Shallow models for non-iterative modal logics, In Andreas Dengel, Karsten Berns, Thomas Breuel, Frank Bomarius, Thomas Roth-Berghofer, eds.: Advances in Artificial Intelligence (KI 2008), Lecture Notes in Artificial Intelligence, vol. 5243, pp. 324–331, Springer, 2008. Full version available as e-print arXiv:0802.0116 [preprint]
Bibtex Entry:
@InProceedings{SchroderPattison08d,
author = {Lutz Schr{\"o}der and Dirk Pattinson},
title = {Shallow models for non-iterative modal logics},
year = {2008},
editor = {Andreas Dengel and Karsten Berns and Thomas Breuel and Frank Bomarius and Thomas Roth-Berghofer},
booktitle = {Advances in Artificial Intelligence (KI 2008)},
publisher = {Springer},
series = {Lecture Notes in Artificial Intelligence},
volume = {5243},
pages = {324-331},
keywords = {Modal logic coalgebra agent shallow model PSPACE decision procedures},
url = {http://dx.doi.org/10.1007/978-3-540-85845-4_40},
comment = { <a href = "http://www8.informatik.uni-erlangen.de/~schroeder/papers/nonitPSP.pdf"> [preprint] </a>},
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.
},
note = {<a href="http://arxiv.org/abs/0802.0116">Full version</a> available as e-print arXiv:0802.0116},
}