Complexity of logics for multi-agent systems with restricted modal context

被引：0
|
作者：
Dziubinski, Marcin [1 ]
机构：
[1] Warsaw Univ, Inst Informat, Fac Math Informat & Mech, PL-02097 Warsaw, Poland
来源：
LOGIC JOURNAL OF THE IGPL | 2013年 / 21卷 / 03期
关键词：
multi-agent systems; modal logic; satisfiability; modal context restriction;
D O I：
10.1093/jigpal/jzr040
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
We present a modal context restriction for multimodal logics with iterated modalities combining axioms K, D, 5 and 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 [9], for checking the satisfiability of the formulas with restricted modal context. The case of axiom T is also discussed.
引用
收藏
页码：355 / 379
页数：25
相关论文
共 50 条
  • [1] Forgetting in multi-agent modal logics
    Fang, Liangda
    Liu, Yongmei
    van Ditmarsch, Hans
    ARTIFICIAL INTELLIGENCE, 2019, 266 : 51 - 80
  • [2] Temporal Logics for Multi-Agent Systems
    Henzinger, Thomas A.
    PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18), 2018, : 1 - 1
  • [3] Comparing Semantics of Logics for Multi-Agent Systems
    Valentin Goranko
    Wojciech Jamroga
    Synthese, 2004, 139 : 241 - 280
  • [4] Comparing semantics of logics for multi-agent systems
    Goranko, V
    Jamroga, W
    SYNTHESE, 2004, 139 (02) : 241 - 280
  • [5] Complexity of multi-agent systems behavior
    Dekhtyar, M
    Dikovsky, A
    Valiev, M
    LOGICS IN ARTIFICIAL INTELLIGENCE 8TH, 2002, 2424 : 125 - 136
  • [6] Complexity measurement of multi-agent systems
    Marir, Toufik
    Mokhati, Farid
    Bouchelaghem-Seridi, Hassina
    Tamrabet, Zouheyr
    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, 8732 : 188 - 201
  • [7] Disjunctive Normal Form for Multi-Agent Modal Logics Based on Logical Separability
    Fang, Liangda
    Wang, Kewen
    Wang, Zhe
    Wen, Ximing
    THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2019, : 2817 - 2826
  • [8] Strategies in Spatio-Temporal Logics for Multi-agent Systems
    Bottoniet, Paolo
    Labella, Anna
    Perellie, Giuseppe
    LEVERAGING APPLICATIONS OF FORMAL METHODS, VERIFICATION AND VALIDATION: REOCAS COLLOQUIUM IN HONOR OF ROCCO DE NICOLA, PT I, ISOLA 2024, 2025, 15219 : 287 - 305
  • [9] Preface to the special issue on computational logics in multi-agent systems
    Dix, Juergen
    Leite, Joao
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2011, 62 (1-2) : 1 - 5
  • [10] Periodic communication logics for the decentralized control of multi-agent systems
    Sun, YS
    Lemmon, MD
    2005 IEEE INTERNATIONAL CONFERENCE ON CONTROL APPLICATIONS (CCA), VOLS 1AND 2, 2005, : 1431 - 1434
12345