Taming the complexity of linear time BDI logics

Nils Bulling, Koen V. Hindriks

Research output: Contribution to ConferencePaperAcademic


Reasoning about the mental states of agents is important in various settings, and has been recognized as vital for teamwork. But the complexity of some of the more well-known agent logics that facilitate reasoning about mental states prohibits the use of these logics in practice. An alternative is to investigate fragments of these logics that have a lower complexity but are still expressive enough for reasoning about the mental states of (other) agents. We explore this alternative and take as our starting point the linear time variant of BDI logic (BDIltl). We summarize some of the relevant known complexity results for e.g. LTL, KD45n, and BDIltl itself. We present a tableau-based method for establishing complexity bounds, and provide a map of the complexity of (various fragments of) BDIltl- Finally, we identify a few fragments that may be usefully applied for reasoning about mental states. Categories and Subject Descriptors 1.2.11 [Artificial Intelligence]: Distributed Artificial Intelligence-Multiagent Systems; 1.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods-Modal logic General Terms Theory, Verification.

Original languageEnglish
Number of pages8
Publication statusPublished - 1 Jan 2011
Externally publishedYes
Event10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China
Duration: 2 May 20116 May 2011


Conference10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
Country/TerritoryTaiwan, Province of China


  • Complexity
  • Linear time BDI logic
  • Reasoning about mental states
  • Satisfiability


Dive into the research topics of 'Taming the complexity of linear time BDI logics'. Together they form a unique fingerprint.

Cite this