The complexity of reasoning about knowledge and time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of reasoning about knowledge and time

Full text

Pdf (875 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 304 - 315

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

J Y Halpern	IBM Almaden Research Center, San Jose, CA
M Y Vardi	IBM Almaden Research Center, San Jose, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 32, Citation Count: 17

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/12130.12161 What is a DOI?

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.

	Ab	Karl Raymond Abrahamson, Decidability and expressiveness of logics of processes, 1980
	CM	K. Mani Chandy , Jayadev Misra, How processes learn, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.204-214, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323615]
	CE	Edmund M. Clarke , E. Allen Emerson, Design and Synthesis of Synchronization Skeletons Using Branching-Time Temporal Logic, Logic of Programs, Workshop, p.52-71, May 01, 1981
	DM	C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
	EH1	E. A. Emerson , Joseph Y. Halpern, Decision procedures and expressiveness in the temporal logic of branching time, Journal of Computer and System Sciences, v.30 n.1, p.1-24, Feb. 1985 [doi>10.1016/0022-0000(85)90001-7]
	EH2	E. Allen Emerson , Joseph Y. Halpern, “Sometimes” and “not never” revisited: on branching versus linear time temporal logic, Journal of the ACM (JACM), v.33 n.1, p.151-178, Jan. 1986 [doi>10.1145/4904.4999]
	FHV	R. Fagin, J.Y. Halpern, and M.Y. Vardi, A model-theoretic analysis of knowledge, Proc. 25th Annual 1EEE Syrup. on Foundations of Computer Science, 1984, pp. 268-278.
	FI	M Fischer , N Immerman, Foundations of knowledge for distributed systems, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.171-185, March 1986, Monterey, California, United States
	GPSS	Dov Gabbay , Amir Pnueli , Saharon Shelah , Jonathan Stavi, On the temporal analysis of fairness, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.163-173, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567462]
	HF	Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323617]
	HM1	Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
	HM2	J. Y. Halpern and Y.O. Moses, A guide to the modal logics of knowledge and belief: preliminary report, Proc. 9th International Joint Conference n Artificial Intelligence, 1985, pp. 480--490.
	HR	J.Y. Halpern and J.H. Reif, The propositional dynamic logic of deterministic, wellstructured programs, Theoretical Computer Science 27, 1983, pp. 127-165.
	Ha	David Harel, Recurring dominoes: making the highly undecidable highly understandable, Selected papers of the international conference on "foundations of computation theory" on Topics in the theory of computation, p.51-71, December 1985, Borgholm, Sweden
	HPS	D. Hare1, A. Pnueli, and J. Slavi, Propositional dynamic logic of nonregular programs, J. Computer and Systems Science, 26:2, 1983, pp. 222-243.
	HPV	D. Harel, A. Pnueli, and M.Y. Vardi, Twodimensional temporal logic and PDL with intersection, unpublished.
	LR	R Ladner , J Reif, The logic of distributed protocols, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.207-222, March 1986, Monterey, California, United States
	La1	L. Lamport, What good is temporal logic?, Information Processing 83 (ed. R.E.A. Mason), Elsevier Publishers, 1983, pp. 657-668.
	La2	Leslie Lamport, "Sometime" is sometimes "not never": on the temporal logic of programs, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.174-185, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567463]
	Leh1	Daniel Lehmann, Knowledge, common knowledge and related puzzles (Extended Summary), Proceedings of the third annual ACM symposium on Principles of distributed computing, p.62-67, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806736]
	Leh2	D.J. Lehmann, Talk given at the 3rd ACM Syrup. on Principles of Distributed Computing, August, 1984.
	MW	Zohar Manna , Pierre Wolper, Synthesis of Communicating Processes from Temporal Logic Specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.1, p.68-93, Jan. 1984 [doi>10.1145/357233.357237]
	Mi	P. Milgrom, An Axiomatic characterization of common knowledge, Econometrica, 49:1, 1981, pp. 219-222.
	PR	Rohit Parikh , R. Ramanujam, Distributed Processes and the Logic of Knowledge, Proceedings of the Conference on Logic of Programs, p.256-268, June 17-19, 1985
	PSL	M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
	Pn	Amir Pnueli, Linear and Branching Structures in the Semantics and Logics of Reactive Systems, Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.15-32, July 15-19, 1985
	Ro	S J Rosenschein, Formal theories of knowledge in AI and robotics, New Generation Computing, v.3 n.4, p.345-357, 1985 [doi>10.1007/BF03037076]
	RK	S Rosenschein , L Kaelbling, The synthesis of digital machines with provable epistemic properties, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.83-98, March 1986, Monterey, California, United States
	Sa	M. Sato, A study of Kripke-style methods of some modal logics by Gentzen's sequential method, Publications Research Institute for Mathematical Sciences, Kyoto University, 13:2, 1977.
	sc	A. P. Sistla , E. M. Clarke, The complexity of propositional linear temporal logics, Journal of the ACM (JACM), v.32 n.3, p.733-749, July 1985 [doi>10.1145/3828.3837]
	vs	M Y Vardi , L Stockmeyer, Improved upper and lower bounds for modal logics of programs, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.240-251, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22173]
	vw	Moshe Y. Vardi , Pierre Wolper, Automata theoretic techniques for modal logics of programs: (Extended abstract), Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.446-456, December 1984 [doi>10.1145/800057.808711]

CITED BY 17

	E. A. Emerson , T. Sadler , J. Srinivasan, Efficient temporal reasoning (extended abstract), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.166-178, January 11-13, 1989, Austin, Texas, United States
	Joseph Halpern , Vardi, Reasoning about knowledge and time in asynchronous systems, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.53-65, May 02-04, 1988, Chicago, Illinois, United States
	Steven M. German , A. Prasad Sistla, Reasoning about systems with many processes, Journal of the ACM (JACM), v.39 n.3, p.675-735, July 1992
	Joseph Y. Halpern, A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.269-280, August 10-12, 1987, Vancouver, British Columbia, Canada
	Ronen I. Brafman , Jean-Claude Latombe , Yoram Moses , Yoav Shoham, Applications of a logic of knowledge to motion planning under uncertainty, Journal of the ACM (JACM), v.44 n.5, p.633-668, Sept. 1997
	Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi, A model-theoretic analysis of knowledge, Journal of the ACM (JACM), v.38 n.2, p.382-428, April 1991
	Brandon Bennett , Clare Dixon , Michael Fisher , Ullrich Hustadt , Enrico Franconi , Ian Horrocks , Maarten De Rijke, Combinations of Modal Logics, Artificial Intelligence Review, v.17 n.1, p.1-20, March 2002
	P. C. Attie , E. A. Emerson, Synthesis of concurrent systems with many similar sequential processes (extended abstract), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.191-201, January 11-13, 1989, Austin, Texas, United States
	Clare Dixon , Michael Fisher , Alexander Bolotov, Clausal resolution in a logic of rational agency, Artificial Intelligence, v.139 n.1, p.47-89, July 2002
	Michael Burrows , Martín Abadi , Roger Needham, Authentication: a practical study in belief and action, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
	Edith Spaan, Nexttime is not necessary, Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledge, March 04-07, 1990, Pacific Grove, California
	Paul F. Syverson, An epistemic logic of situations: extended abstract, Proceedings of the 5th conference on Theoretical aspects of reasoning about knowledge, p.109-121, March 13-16, 1994, Pacific Grove, California
	Joseph Y. Halpern, On ambiguities in the interpretation of game trees, Proceedings of the 6th conference on Theoretical aspects of rationality and knowledge, March 17-20, 1996, The Netherlands
	Kaile Su , Abdul Sattar , Guido Governatori , Qingliang Chen, A computationally grounded logic of knowledge, belief and certainty, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands
	Joeri Engelfriet , Catholijn M. Jonker , Jan Treur, Compositional Verification of Multi-Agent Systems in Temporal Multi-Epistemic Logic, Journal of Logic, Language and Information, v.11 n.2, p.195-225, Spring 2002
	Kaile Su , Abdul Sattar , Han Lin , Mark Reynolds, A modal logic for beliefs and pro attitudes, Proceedings of the 22nd national conference on Artificial intelligence, p.496-501, July 22-26, 2007, Vancouver, British Columbia, Canada
	Kaile Su , Abdul Sattar, An extended interpreted system model for epistemic logics, Proceedings of the 23rd national conference on Artificial intelligence, p.554-559, July 13-17, 2008, Chicago, Illinois