zbMATH — the first resource for mathematics

Complexity of logics for multi-agent systems with restricted modal context. (English) Zbl 1277.68255
Summary: We present a modal context restriction for multimodal logics with iterated modalities combining axioms \(\mathbf K\), \(\mathbf D\), \(\mathbf 5\) and \(\mathbf{45}\), for which the satisfiability problem is PSPACE-complete and putting additional restriction on the modal depth of formulas makes it NPTIME-complete. We propose an extension of the tableau method, as presented in [J. Y. Halpern and Y. Moses, Artif. Intell. 54, No. 3, 319–379 (1992; Zbl 0762.68029)], for checking the satisfiability of the formulas with restricted modal context. The case of axiom \(\mathbf T\) is also discussed.
68T27 Logic in artificial intelligence
03B45 Modal logic (including the logic of norms)
03B62 Combined logics
68T42 Agent technology and artificial intelligence
Full Text: DOI