Progress measures and stack assertions for fair termination

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Progress measures and stack assertions for fair termination

Full text

Pdf (1.11 MB)

Source

Annual ACM Symposium on Principles of Distributed Computing archive
Proceedings of the eleventh annual ACM symposium on Principles of distributed computing table of contents

Vancouver, British Columbia, Canada

Pages: 229 - 240

Year of Publication: 1992

ISBN:0-89791-495-3

Author

Nils Klarlund

IBM T.J. Watson Research Center, PO BOX 704, Yorktown Heights, New York

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/135419.135462 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.

	AFK88	K.R. Apt, N. Francez, and S. Katz. Appraising fairness in languages for distributed programming. Distributed Computing, 2:226-241, 1988.
	AL91	Martín Abadi , Leslie Lamport, The existence of refinement mappings, Theoretical Computer Science, v.82 n.2, p.253-284, May 31, 1991 [doi>10.1016/0304-3975(91)90224-P]
	AO83	K.R. Apt and E.-R. Olderog. Proof rules and transformations dealing with fairness. Science of Computer Programming, 3:65-100, 1983.
	AP86	K. R. Apt , G. D. Plotkin, Countable nondeterminism and random assignment, Journal of the ACM (JACM), v.33 n.4, p.724-767, Oct. 1986 [doi>10.1145/6490.6494]
	APS84	K.R. Apt, A. Pnueli, and J. Stavi. Fair termination revisited with delay. Theoretical Computer Science, 33:65- 84, 1984.
	DH86	I. Dayan and D. Harel. Fair termination with cruel schedulers. Fundamenia Informatica, 9:1-12, 1986.
	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]
	Flo67	R. Floyd. Assigning meaning to programs. In Mathematical Aspects of Compuler Science XiX, pages 19-32. American Mathematical Society, 1967.
	Fra86	Nissim Francez, Fairness, Springer-Verlag New York, Inc., New York, NY, 1986
	GFMdRv85	Orna Grumberg , Nissim Francez , Johann A. Makowsky , Willem P. de Roever, A proof rule for fair termination of guarded commands, Information and Control, v.66 n.1-2, p.83-102, July/Aug. 1985 [doi>10.1016/S0019-9958(85)80014-0]
	GH82	Yuri Gurevich , Leo Harrington, Trees, automata, and games, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.60-65, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802177]
	Gri81	David Gries, The Science of Programming, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	Har86	David Harel, Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness, Journal of the ACM (JACM), v.33 n.1, p.224-248, Jan. 1986 [doi>10.1145/4904.4993]
	KK91	N. Klarlund and D. Kozen. Rabin measures and their applications to fairness and automata theory. In Proc. Sixth Syrup. on Logic in Computer Science. IEEE, 1991.
	Kla	Nils Klarlund, Liminf Progress Measures, Proceedings of the 7th International Conference on Mathematical Foundations of Programming Semantics, p.477-491, March 25-28, 1991
	Kla90	Nils Klarlund, Progress measures and finite arguments for infinite computations, 1990
	Kla91	Nils Klarlund, Progress measures for complementation of &ohgr;-automata with applications to temporal logic, Proceedings of the 32nd annual symposium on Foundations of computer science, p.358-367, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185391]
	Kla92	N. Klarlund. Progress measures, immediate determinacy, and a subset construction for tree automata. In Proc. Seventh Syrup. on Logic in Computer Science, 1992. To appear.
	KS93	Nils Klarlund , Fred B. Schneider, Proving nondeterministically specified safety properties using progress measures, Information and Computation, v.107 n.1, p.151-170, Nov. 1993 [doi>10.1006/inco.1993.1064]
	LPS81	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
	Mai89	M.G. Main. Complete proof rules for strong fairness and strong extremefairness. Technical Report CU-CS-447- 89, Department of Computer Science, University of Colorado, 1989.
	Mor90	Joseph M. Morris, Temporal predicate transforms and fair termination, Acta Informatica, v.27 n.4, p.287-313, 1990
	Mos74	Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
	MP91	Zohar Manna , Amir Pnueli, Completing the temporal picture, Theoretical Computer Science, v.83 n.1, p.97-130, June 21, 1991
	Rog67	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	Saf92	Shmuel Safra, Exponential determinization for &ohgr;-automata with strong-fairness acceptance condition (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.275-282, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129739]
	SdRG89	F. A. Stomp , W. P. de Roever, The &mgr;-calculus as an assertion-language for fairness arguments, Information and Computation, v.82 n.3, p.278-322, Sep. 1989 [doi>10.1016/0890-5401(89)90004-7]
	Sis91	A. P. Sistla, Proving correctness with respect to nondeterministic safety specifications, Information Processing Letters, v.39 n.1, p.45-49, July 12, 1991 [doi>10.1016/0020-0190(91)90061-L]
	Var87	M. Vardi. Verification of concurrent programs: The automata-theoretic framework. In Proc. Syrup. on Logic in Computer Science. IEEE, 1987.