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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (328 KB)

Source

International Conference on Autonomous Agents archive
Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems - Volume 2 table of contents

Budapest, Hungary

SESSION: Commitments/logical approaches table of contents

Pages 969-976

Year of Publication: 2009

ISBN:978-0-9817381-7-8

Authors

Valentin Goranko	University of the Witwatersrand, Johannesburg, South Africa
Dmitry Shkatov	University of the Witwatersrand, Johannesburg, South Africa

Sponsors

: The Foundation for Intelligent Physical Agents
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
: Drexel University
: Wiley -- Blackwell Ltd

Publisher

International Foundation for Autonomous Agents and Multiagent Systems Richland, SC

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 20, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi, What can machines know?: On the properties of knowledge in distributed systems, Journal of the ACM (JACM), v.39 n.2, p.328-376, April 1992 [doi>10.1145/128749.150945]
	2	Valentin Goranko , Dmitry Shkatov, Tableau-Based Procedure for Deciding Satisfiability in the Full Coalitional Multiagent Epistemic Logic, Proceedings of the 2009 International Symposium on Logical Foundations of Computer Science, p.197-213, January 03-03, 2009, Deerfield Beach, FL [doi>10.1007/978-3-540-92687-0_14]
	3	Joseph Y. Halpern , Yoram Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, v.54 n.3, p.319-379, April 1992 [doi>10.1016/0004-3702(92)90049-4]
	4	Joseph Y. Halpern , Moshe Y. Vardi, The complexity of reasoning about knowledge and time. I. lower bounds, Journal of Computer and System Sciences, v.38 n.1, p.195-237, February 1989 [doi>10.1016/0022-0000(89)90039-1]
	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.

INDEX TERMS

General Terms:
Theory

Keywords:
decision procedures, logics for multi-agent systems, tableaux

Collaborative Colleagues:

Valentin Goranko: colleagues

Dmitry Shkatov: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player