×

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.
MSC:
68T27 Logic in artificial intelligence
03B45 Modal logic (including the logic of norms)
03B62 Combined logics
68T42 Agent technology and artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI