Reasoning about fair concurrent programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Reasoning about fair concurrent programs

Full text

Pdf (933 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: 283 - 294

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

C Courcoubetis	AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ
M Y Vardi	IBM Almaden Research Center, Department K55/801, 650 Harry Road, San Jose, CA
P Wolper	AT&T Bell Laboratories, 600 Mountain ave., Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 8, Citation Count: 3

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.12159 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.

	Ab80	Karl Raymond Abrahamson, Decidability and expressiveness of logics of processes, 1980
	BMP81	Mordechai Ben-Ari , Zohar Manna , Amir Pnueli, The temporal logic of branching time, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.164-176, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567551]
	CES83	E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite state concurrent system using temporal logic specifications: a practical approach, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.117-126, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567080]
	EC82	E.A. Emerson, E. M. Clarke, "Using Branching Time Logic to Synthesize Synchronization Skeletons", Science of Computer Programming, 2(1982), pp. 241-266.
	EH85	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]
	EH83	E. Allen Emerson , Joseph Y. Halpern, "Sometimes" and "not never" revisited: on branching versus linear time (preliminary report), Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.127-140, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567081]
	EL85a	E.A. Emerson, C.L. Lei, "Temporal Model Checking under Generalized Fairness Constralnts". Proc. 18th Hawaii Int'l Conference on System Sciences, 1985.
	EL85b	E. Allen Emerson , Chin-Laung Lei, Modalities for model checking (extended abstract): branching time strikes back, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.84-96, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318620]
	Ern83	E. A. Emerson, "Alternative Semantics for Temporal Logic", Theoretical Computer Science, 26(1983), pp. 120-130.
	Em85a	E. Allen Emerson, Automata, Tableaux and Temporal Logics (Extended Abstract), Proceedings of the Conference on Logic of Programs, p.79-88, June 17-19, 1985
	ES84	E.A. Emerson, A.P. Sistla,"Deciding Branching Time Logic", Information and Control, 61(1984), pp. 175-201.
	FK84	Nissim Francez , Dexter Kozen, Generalized fair termination, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.46-53, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800515]
	Ga76	D.M. Gabbay, "Investigation in Modal and Tense Logic" Reidel, 1976.
	GPSS80	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]
	HS84	Sergiu Hart , Micha Sharir(, Probabilistic temporal logics for finite and bounded models, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.1-13, December 1984 [doi>10.1145/800057.808660]
	JL77	N.D. Jones, W.T. Laaser, "Complete Problems in Deterministic Polynomial Time", Theoretical Computer Science 3(1977), pp. 105-117.
	Kr 84	S. Krans, "The decision problem for TG' (in Hebrew), M.Se. Thesis, The Hebrew University in Jerusalem, 1984.
	KSK66	J.G. Kemeny, J.L. Snell, A.W. Knapp, "Denumerable Markov Chains" D. van Nostrand Company, 1966.
	KL83	S. Kraus, D. Lehmann, "Decision Procedures for Time and Chance", Proc. 24th IEEE Syrup. on Foundations of Computer Science, Tucson, 1983, pp. 202-209.
	La80	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]
	LP85	Orna Lichtenstein , Amir Pnueli, Checking that finite state concurrent programs satisfy their linear specification, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.97-107, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318622]
	LPSSl	Daniel J. Lehmann , Amir Pnueli , Jonathan Stavi, Impartiality, Justice and Fairness: The Ethics of Concurrent Termination, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.264-277, July 13-17, 1981
	LS82	D. Lehman, S. Shelah, "Reasoning with Time and Chance", Information and Control 53(1982), pp. 165.-198.
	McN66	R. McNaughton, "Testing and Generating Infinite Sequences by a Finite Automaton", Information and Control 9 (1966), pp. 521-530
	MWS4	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]
	Pn77	A. Pnueli, "The Temporal Logic of Programs", Proe. 8th IEEE Symp. on Foundations of Computer Science, Providence, 1977, pp. 46.-57.
	Pn81	A. Pnueli, "The Temporal Logic of Concurrent Programs", Theoretical Computer Science 13(1980, pp. 45-60.
	Pn83	Amir Pnueli, On the extremely fair treatment of probabilistic algorithms, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.278-290, December 1983 [doi>10.1145/800061.808757]
	QS82	J.P. Queille, J. Sifakis, "Fairness and Related Properties in Transition Systems'; Research Report #292, IMA.G, Grenoble, 1982.
	RAT0	M.O. Rabin, "Weakly Definable Relations and Special Automata", Proe. Symp. Math. Logic and Foundations of Set Theory (Y. Bar-Hillel, ed.), North-Holland, 1970, pp. 1-23.
	Ra72	M.O. Rabin, "Automata on Infinite Objects and Church's Problem", Proe. Regional AMS Conf. Series in Math. 13(1972), pp. 1-22.
	RS59	M. O. Rabin, D. Scott, "Finite Automata and their Decision Problems", IBM J. Res. 6~ Dev., 3(1959), pp 114-125.
	st82	R.S. Streett, "Propositional Dynamic Logic of Looping and Converse", Information and Control 54(1982), pp. 121-141.
	vs85	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]
	vw84	Moshe Y Vardi , Pierre Wolper, Automata-Theoretic techniques for modal logics of programs, Journal of Computer and System Sciences, v.32 n.2, p.183-221, April 1986 [doi>10.1016/0022-0000(86)90026-7]
	WV83	P. Wolper, M. Y. Vardi, A. P. Sistla, "Reasoning about Infinite Computation Paths", Proc. 24th IEEE Syrup. on Foundations of Computer Science, Tucson, 1983, pp. 185-194.

CITED BY 3

	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
	R. P. Kurshan, The complexity of verification, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.365-371, May 23-25, 1994, Montreal, Quebec, Canada
	Shmuel Katz , Doron Peled, Interleaving set temporal logic, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.178-190, August 10-12, 1987, Vancouver, British Columbia, Canada