Schedulers as abstract interpretations of higher-dimensional automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Schedulers as abstract interpretations of higher-dimensional automata

Full text

Pdf (1.34 MB)

Source

ACM/SIGPLAN Workshop Partial Evaluation and Semantics-Based Program Manipulation archive
Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation table of contents

La Jolla, California, United States

Pages: 134 - 145

Year of Publication: 1995

ISBN:0-89791-720-0

Author

Eric Goubault

LIENS, École Normale Supérieure, 45 rue d'Ulm, 75230 Paris, Cedex 05, FRANCE

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	1	Brian A. LaMacchia , Andrew M. Odlyzko, Solving Large Sparse Linear Systems over Finite Fields, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.109-133, August 11-15, 1990
	2	Hagit Attiya , Roy Friedman, A correctness condition for high-performance multiprocessors (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.679-690, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129778]
	3	H. J. Baues. Algebraic homotopy. In Cambmdge Studzes in Advanced Mathematics, volume 15. Cambridge University Press, 1989.
	4	Marek Antoni Bednarczyk, Categories of asynchronous systems, 1987
	5	F. Bracho, M. Droste, and D. Kuske. Representation of computations in concurrent automata by dependence orders. Technical report, Technische Universitat Dresden, 1994.
	6	Scott D. Carson , Paul F. Reynolds, Jr., The geometry of semaphore programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.1, p.25-53, Jan. 1987 [doi>10.1145/9758.9759]
	7	Patrick Cousot , Radhia Cousot, Systematic design of program analysis frameworks, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.269-282, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567778]
	8	P. Cousot and R. Cousot. Higher-order abstract interpretation (and application to comportment analysis generalizing strictness, termination, projection and per analysis of functional languages). In Proceedings of the I994 International Conference on Computer Languages, pages 95-112. IEEE Computer Society Press, May 1994.
	9	Régis Cridlig , Eric Goubault, Semantics and Analysis of Linda-Based Languages, Proceedings of the Third International Workshop on Static Analysis, p.72-86, September 22-24, 1993
	10	E.W. Dijkstra. Cooperating Sequential Processes. Academic Press, 1968.
	11	E. Goubault. Domains of higher-dimensional automata. In Vertag.
	12	Eric Goubault , Thomas P. Jensen, Homology of Higher Dimensional Automata, Proceedings of the Third International Conference on Concurrency Theory, p.254-268, August 24-27, 1992
	13	J. Gunawardena. Homotopy and concurrency. In Bulletin of the EATCS, number 54, pages 184-193, October 1994.
	14	E. Harcourt, J. Mauney, and T. Cook. From processor timing specifications to static instruction scheduling. In Proc. of the Static Analysis Symposium'9~. Springer-Verlag, 1994.
	15	M. Herlihy. A tutorial on algebraic topology and distributed computation. Technical report, presented at UCLA, 1994.
	16	Maurice Herlihy , Nir Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.111-120, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167125]
	17	Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195144]
	18	S. Lang. Algebra. Addison-Wesley, third edition, 1993.
	19	Shun-Tak Leung , John Zahorjan, Improving the performance of runtime parallelization, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.83-91, May 19-22, 1993, San Diego, California, United States
	20	S. Mac Lane. Homology. In Die GrundIehren der Mathematishen Wissenscha}ten in EinzeIdarstellungen, volume Band 114. Springer Verlag, 1963.
	21	S. Mac Lane. Categories .for the working mathematician. Springer-Verlag, 1971.
	22	W. S. Massey. A basic course in algebraic topology, in Graduate Texts in Mathematics, number 127. Springer-Verlag, 1991.
	23	Antoni W. Mazurkiewicz, Basic notions of trace theory, Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, p.285-363, May 30-June 03, 1988
	24	P. Peterson , David A. Padua, Dynamic Dependence Analysis: A Novel Method for Data Depndence Evaluation, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.64-81, August 03-05, 1992
	25	C. Pomerance and J. W. Smith. Reduction of huge, sparse matrices over finite gtelds via created catastrophes. Expcmmental Mathematics, 1(2):89-94, 1992.
	26	Vaughn Pratt, Modeling concurrency with geometry, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.311-322, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99625]
	27	Todd A. Proebsting , Christopher W. Fraser, Detecting pipeline structural hazards quickly, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.280-286, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177904]
	28	John Hamilton Reppy, Higher-order concurrency, Cornell University, Ithaca, NY, 1992
	29	Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
	30	M.W. Shields. Concurrent machines. Computer Journal, 28, 1985.
	31	Eugene W. Stark, Concurrent transition systems, Theoretical Computer Science, v.64 n.3, p.221-269, 29 May 1989 [doi>10.1016/0304-3975(89)90050-9]
	32	Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
	33	R. van Glabbeek. Bisimulation semantics for higher dimensional automata. Technical report, Stanford University, 1991.
	34	G. Winskel and M. Nielsen. Models for concurrency, volume 3 of Handbook of Logic in Computer Science, pages 100-200. Oxford University Press, 1994.

CITED BY 8

	Thao Dang , Philippe Gerner, Scheduling for multi-threaded real-time programs via path planning, Proceedings of the 6th ACM & IEEE International conference on Embedded software, October 22-25, 2006, Seoul, Korea
	Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
	R. J. van Glabbeek, On the expressiveness of higher dimensional automata, Theoretical Computer Science, v.356 n.3, p.265-290, 30 May 2006
	R. J. van Glabbeek, Erratum: Erratum to “On the expressiveness of higher dimensional automata”, Theoretical Computer Science, v.368 n.1-2, p.168-194, December, 2006
	Vaughan R. Pratt, Transition and cancellation in concurrency and branching time, Mathematical Structures in Computer Science, v.13 n.4, p.485-529, August 2003
	Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
	Vaughan Pratt, Higher dimensional automata revisited, Mathematical Structures in Computer Science, v.10 n.4, p.525-548, August 2000
	Lisbeth Fajstrup , Martin Raußen , Eric Goubault, Algebraic topology and concurrency, Theoretical Computer Science, v.357 n.1, p.241-278, 25 July 2006