skip to main content
10.5555/1558109.1558147guideproceedingsArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article
Free access

Tableau-based decision procedure for full coalitional multiagent temporal-epistemic logic of linear time

Published: 10 May 2009 Publication History

Abstract

We develop a tableau-based decision procedure for the full coalitional multiagent temporal-epistemic logic of linear time CMATEL(CD+LT). It extends LTL with operators of common and distributed knowledge for all coalitions of agents. The tableau procedure runs in exponential time, matching the lower bound obtained by Halpern and Vardi for a fragment of our logic, thus providing a complexity-optimal decision procedure for CMATEL(CD+LT).

References

[1]
R. Fagin, J. Y. Halpern, and M. Y. Vardi. What can machines know? On the properties of knowledge in distributed systems. Journal of the ACM, 39(2):328--376, April 1992.
[2]
V. Goranko and D. Shkatov. Tableau-based procedure for deciding satisfiability in the full coalitional multiagent epistemic logic. In S. Artemov and A. Nerode, editors, Proc. of the Symposium on Logical Foundations of Computer Science (LFCS 2009), volume 5407 of Lecture Notes in Computer Science, pages 197--213. Springer-Verlag, 2009.
[3]
J. Y. Halpern and Y. Moses. A guide to completeness and complexity for modal logics of knowledge and belief. Artificial Intelligence, 54:319--379, 1992.
[4]
J. Y. Halpern and M. Y. Vardi. The complexity of reasoning about knowledge and time I: Lower bounds. Journal of Computer and System Sciences, 38(1):195--237, 1989.
[5]
V. R. Pratt. A near optimal method for reasoning about action. Journal of Computer and System Sciences, 20:231--254, 1980.
[6]
W. van der Hoek and J.-J. C. Meyer. Making some issues of implicit knowledge explicit. International Journal of Foundations of Computer Science, 3(2):193--224, 1992.
[7]
P. Wolper. The tableau method for temporal logic: an overview. Logique et Analyse, 28(110--111):119--136, 1985.

Cited By

View all
  • (2014)Satisfiability of alternating-time temporal epistemic logic through tableauxProceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning10.5555/3031929.3031978(398-407)Online publication date: 20-Jul-2014
  1. Tableau-based decision procedure for full coalitional multiagent temporal-epistemic logic of linear time

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image Guide Proceedings
    AAMAS '09: Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2
    May 2009
    730 pages
    ISBN:9780981738178

    Sponsors

    • Drexel University
    • Wiley-Blackwell
    • Microsoft Research: Microsoft Research
    • Whitestein Technologies
    • European Office of Aerospace Research and Development, Air Force Office of Scientific Research, United States Air Force Research Laboratory
    • The Foundation for Intelligent Physical Agents

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 10 May 2009

    Author Tags

    1. decision procedures
    2. logics for multi-agent systems
    3. tableaux

    Qualifiers

    • Research-article

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)21
    • Downloads (Last 6 weeks)3
    Reflects downloads up to 07 Mar 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2014)Satisfiability of alternating-time temporal epistemic logic through tableauxProceedings of the Fourteenth International Conference on Principles of Knowledge Representation and Reasoning10.5555/3031929.3031978(398-407)Online publication date: 20-Jul-2014

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media