Look ma, no hashing, and no arrays neither

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Look ma, no hashing, and no arrays neither

Full text

Pdf (1.21 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Orlando, Florida, United States

Pages: 143 - 154

Year of Publication: 1991

ISBN:0-89791-419-8

Authors

Jiazhen Cai	New York University/Courant Institute, New York, NY and University of Wisconsin, Madison, WI
Robert A. Paige	New York University/Courant Institute, New York, NY and University of Wisconsin, Madison, WI

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 26, 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/99583.99605 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Aho, A., Sethi, R. and UIIman, J., Compilers, Addison- Wesley, 1986.
	3	Allen, F. E., Cocke, J., and Kennedy, K., "Reduction of Operator Strength," in Program Flow Analysis, ed. Muchnick, S. and Jones, N., pp. 79-101, Prentice Hall, 1981.
	4	B. Alpern , M. N. Wegman , F. K. Zadeck, Detecting equality of variables in programs, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73561]
	5	Carter, J. and Wegman, M., "Universal Classes of Hash Functions," JCSS, vol. 18, no. 2, pp. 143-154, 1979.
	6	John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
	7	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	8	Cytron, R., Lowry, A., and Zadeck, K., "Code Motion of Control Structures in High-leveI Languages," IBM Research Center/Yorktown Heights, 1985.
	9	Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980 [doi>10.1145/322217.322228]
	10	Christoph M. Hoffmann , Michael J. O'Donnell, Pattern Matching in Trees, Journal of the ACM (JACM), v.29 n.1, p.68-95, Jan. 1982 [doi>10.1145/322290.322295]
	11	Hopcroft, J., "An n log n Algorithm for Minimizing States in a Finite Automaton," in Theory of Machines and Computations, ed. Kohavi and Paz, pp. 189-196, Academic Press, New York, 1971.
	12	Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
	13	Mairson, H., "The Program Complexity of Searching a Table," in 24th IEEE FOCS, pp. 40-47, Nov., 1983.
	14	R. Paige, Symbolic finite differencing, part I (invited lecture), Proceedings of the third European symposium on programming on ESOP '90, p.36-56, May 1990, Copenhagen, Denmark
	15	Paige, R., "Real-time Simulation of a Set Machine on a RAM," in ICCI '89, ed. W. Koczkodaj, Computing and Information, Vol II, pp. 69-73, 1989.
	16	Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
	17	Paige, R., Tarjan, R., and Bonic, R., "A Linear Time Solution to the Single Function Coarsest Partition Problem," TCS, vol. 40, no. 1, pp. 67-84, Sep, 1985.
	18	Eduardo Pelegri-Llopart , Susan J. Graham, Rewrite systems, pattern matching, and code generation, 1988
	19	Stearns, R., "Deterministic top-down parsing," in Proc. 5th Princeton Conf. on Information Sciences and Systerns, pp. 182-188, 1971.
	20	Tarjan, R., "Depth first search and linear graph algorithms," SlAM J. Comput, vol. 1, no. 2, pp. 146-160, 1972.
	21	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	22	Mark N. Wegman , Frank Kenneth Zadeck, Constant propagation with conditional branches, Proceedings of the 12th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.291-299, January 14-16, 1985, New Orleans, Louisiana, United States [doi>10.1145/318593.318659]
	23	Yang, W., Horwitz, S., and Reps, T., "Detecting program components with equivalent behaviors," TR-840, Computer Sciences Dept., Univ. of Wisconsin, Madison, WI, April 1989.
	24	Wuu Yang , Thomas Reps , Susan Horwitz, A new algorithm for semantics-based program integration, 1990

CITED BY 3

	Keith D. Cooper , L. Taylor Simpson , Christopher A. Vick, Operator strength reduction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.5, p.603-625, September 2001
	Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Fritz Henglein, Generic discrimination: sorting and paritioning unshared data in linear time, ACM SIGPLAN Notices, v.43 n.9, September 2008