Shape analysis as a generalized path problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shape analysis as a generalized path problem

Full text

Pdf (1.23 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: 1 - 11

Year of Publication: 1995

ISBN:0-89791-720-0

Author

Thomas Reps

Computer Sciences Department, University of Wisconsin-Madison, 1210 W. Dayton Street, Madison, WI

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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.215466 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	Assmann, U., "On edge addition rewrite systems and their relevance to program analysis," Unpublished report, GMD Forschungsstelle Karlsruhe, Karlsruhe, Germany (1993).
	2	Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
	3	F. Bancilhon , R. Ramakrishnan, Performance evaluation of data intensive logic programs, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
	4	C. Beeri , R. Ramakrishnan, On the power of magic, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.269-284, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28689]
	5	S. Ceri , G. Gottlob , L. Tanca, What You Always Wanted to Know About Datalog (And Never Dared to Ask), IEEE Transactions on Knowledge and Data Engineering, v.1 n.1, p.146-166, March 1989 [doi>10.1109/69.43410]
	6	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
	7	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	8	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Demand-driven computation of interprocedural data flow, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.37-48, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199461]
	9	Nevin Heintze, Set Based Analysis of ML Programs (Extended Abstract), Carnegie Mellon University, Pittsburgh, PA, 1993
	10	L. J. Hendren , A. Nicolau, Parallelizing Programs with Recursive Data Structures, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.35-47, January 1990 [doi>10.1109/71.80123]
	11	S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
	12	Horwitz, S., Reps, T., and Sagiv, M., "Demand interprocedural dataflow analysis," Unpublished Report, Comp. Sci. Dept., Univ. of Wisconsin, Madison, WI (March 1995).
	13	Jones, N.D. and Muchnick, S.S., "Complexity of flow analysis, inductive assertion synthesis, and a language due to Dijkstra," pp. 380-393 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ (1981).
	14	Jones, N.D. and Muchnick, S.S., "Flow analysis and optimization of Lisp-like structures," pp. 102-131 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones,Prentice-Hall, Englewood Cliffs, NJ ( 1981).
	15	Kasami, J., "An efficient recognition and syntax analysis algorithm for context-free languages," Scientific Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA (1965).
	16	J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
	17	McCarthy, J., "A basis for a mathematical theory of computation," pp. 33-70 in Computer Programming and Formal Systems, ed. Braffort and Hershberg,North-Holland, Amsterdam (1963).
	18	Mogensen, T., "Partially static structures in a self-applicable partial evaluator," pp. 325-347 in Partial Evaluation and Mixed Computation: Proceedings of the IFIP TC2 Workshop on Partial Evaluation and Mixed Computation, (Gammel Avernaes, Denmark, 18-24 October, 1987), ed. D. Bjffrner, A.P. Ershov, N.D. Jones,North- Holland, New York, NY (1988).
	19	Torben Æ Mogensen, Separating binding times in language specifications, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.12-25, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99372]
	20	Ramakrishnan, R., Seshadri, P., Srivastava, D., and Sudarshan, S., "The Coral user manual: A tutorial introduction to Coral," Unpublished documentation, Computer Sciences Department, University of Wisconsin, Madison, WI (1993). (Available via ftp from ftp.cs.wisc.edu.)
	21	Ramakrishnan, R., Seshadri, P., Srivastava, D., and Sudarshan, S., "Coral Release 1. I," Software system, Computer Sciences Department, University of Wisconsin, Madison, WI (May 1994). (Available via ftp from ftp.cs.wisc.edu.)
	22	Reps, T., Sagiv, M., and Horwitz, S., "Interprocedural dataflow analysis via graph reachability," TR 94-14, Datalogisk Institut, University of Copenhagen, Copenhagen, Denmark (April 1994). (Available on the World Wide Web at ftp ://ftp.diku.dk/diku/semantics/papers/D-215. ps.Z.)
	23	Reps, T., "Demand interprocedural program analys~s using logic databases," pp. 163-196 in Applications of Logic Databases, ed. R. Ramakrishnan,Kluwer Academic Publishers, Boston, MA (1994).
	24	Thomas W. Reps, Solving Demand Versions of Interprocedural Analysis Problems, Proceedings of the 5th International Conference on Compiler Construction, p.389-403, April 07-09, 1994
	25	Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
	26	Reynolds, J.C., "Automatic computation of data set definitions," pp. 456-461 in Information Processing 68: Proceedings of the IF1P Congress 68, North-Holland, New York, NY (1968).
	27	J Rohmer , R Lescoeur , J M Kerisit, The Alexander method-a technique for the processing of recursive axioms in deductive databases, New Generation Computing, v.4 n.3, p.273-285, 1986 [doi>10.1007/BF03037407]
	28	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	29	Mihalis Yannakakis, Graph-theoretic methods in database theory, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.230-242, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298576]
	30	Younger, D.H., "Recognition and parsing of context-free languages in time n**3," Information and Control 10 pp. 189-208 (1967).

CITED BY 10

	Swarat Chaudhuri, Subcubic algorithms for recursive state machines, ACM SIGPLAN Notices, v.43 n.1, January 2008
	John Kodumal , Alex Aiken, The set constraint/CFL reachability connection in practice, ACM SIGPLAN Notices, v.39 n.6, May 2004
	David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, ACM SIGPLAN Notices, v.32 n.12, p.74-89, Dec. 1997
	Thomas Reps, Undecidability of context-sensitive data-independence analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.1, p.162-186, Jan. 2000
	Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.1, p.1-50, Jan. 1998
	Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States
	Steven Dawson , C. R. Ramakrishnan , David S. Warren, Practical program analysis using general purpose logic programming systems—a case study, ACM SIGPLAN Notices, v.31 n.5, p.117-126, May 1996
	Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Lunjin Lu, Path Dependent Analysis of Logic Programs, Higher-Order and Symbolic Computation, v.16 n.4, p.341-377, December 2003
	Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States