Variations on the Common Subexpression Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Variations on the Common Subexpression Problem

Full text

Pdf (969 KB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 4 (October 1980) table of contents

Pages: 758 - 771

Year of Publication: 1980

ISSN:0004-5411

Authors

Peter J. Downey	Department of Computer Science, The University of Arizona, Tucson, Arizona
Ravi Sethi	Bell Laboratories, Murray Hill, New Jersey
Robert Endre Tarjan	Bell Laboratories, Murray Hill, New Jersey and Stanford University, Stanford, California

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/322217.322228 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	AHO, A V, BEERI, C, AND ULLMAN, J.D The theory of joins m relational databases. Proc 18th Ann. IEEE Symp on Foundauons of Computer Science, Providence, R 1, 1977, pp 107-113.
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	E. Cardoza , R. Lipton , A. R. Meyer, Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report), Proceedings of the eighth annual ACM symposium on Theory of computing, p.50-54, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803630]
	4	John Cocke, Programming languages and their compilers: Preliminary notes, Courant Institute of Mathematical Sciences, New York University, 1969
	5	Peter Downey , Hanan Samet , Ravi Sethi, Off-line and on-line algorithms for deducing equalities, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.158-170, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512777]
	6	Peter J. Downey , Ravi Sethi, Assignment Commands with Array References, Journal of the ACM (JACM), v.25 n.4, p.652-666, Oct. 1978 [doi>10.1145/322092.322104]
	7	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	8	HOPCROFT, J E, AND KARP, R.M An algorithm for testing the equivalence of finite automata. T~ch. Rep. 71-114, Computer Science Dept, Cornell Umv, Ithaca, N.Y, 1971
	9	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	10	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	11	Dexter Kozen, Complexity of finitely presented algebras, Proceedings of the ninth annual ACM symposium on Theory of computing, p.164-177, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803406]
	12	LIu, L, AND DEMERS, A An efficient algorithm for testing losslessness of.loins in relational database~ Tech Rep 78-351, Computer Science Dept, Cornell Umv, Ithaca, N Y, 1978
	13	Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980 [doi>10.1145/322186.322198]
	14	Derek C. Oppen, Reasoning About Recursively Defined Data Structures, Journal of the ACM (JACM), v.27 n.3, p.403-411, July 1980 [doi>10.1145/322203.322204]
	15	PATERSON, M S, ANt) WEGMAN, M N Linear unification J Comp. Syst Sa. 16 (1978), 158-167.
	16	ROSE, D J, TAR JAN, R E, AND LUI~KER, G S Algorithmic aspects of vertex ehmmation on graphs. SIAM J Comput 5 (1976), 266-283
	17	SETHI, R Scheduling graphs on two processors SIAM J Comput 5 (1976), 73-82
	18	Robert E. Shostak, An algorithm for reasoning about equality, Communications of the ACM, v.21 n.7, p.583-585, July 1978 [doi>10.1145/359545.359570]
	19	Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
	20	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	21	TARSKI, A, MOSTOWSKI, A AND ROBINSON, R M Undeadable Theories North-Holland, Amsterdam, 1953

CITED BY 62

	S S Cosmadakis , P C Kanellakis, Equational theories and database constraints, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.273-284, May 06-08, 1985, Providence, Rhode Island, United States
	Jan Chomicki , Tomasz Imieliński, Finite representation of infinite query answers, ACM Transactions on Database Systems (TODS), v.18 n.2, p.181-223, June 1993
	Robert E. Shostak, Deciding Combinations of Theories, Journal of the ACM (JACM), v.31 n.1, p.1-12, Jan. 1984
	C. Elkan, A decision procedure for conjunctive query disjointness, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-139, March 1989, Philadelphia, Pennsylvania, United States
	Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980
	Jean Gallier , Paliath Narendran , David Plaisted , Stan Raatz , Wayne Snyder, An algorithm for finding canonical sets of ground rewrite rules in polynomial time, Journal of the ACM (JACM), v.40 n.1, p.1-16, Jan. 1993
	R. Ramesh , I. V. Ramakrishnan, Nonlinear pattern matching in trees, Journal of the ACM (JACM), v.39 n.2, p.295-316, April 1992
	Robert Paige, Transformational programming: applications to algorithms and systems, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.73-87, January 24-26, 1983, Austin, Texas
	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984
	David McAllester , Robert Givan, Taxonomic syntax for first order inference, Journal of the ACM (JACM), v.40 n.2, p.246-283, April 1993
	Derek C. Oppen, Reasoning About Recursively Defined Data Structures, Journal of the ACM (JACM), v.27 n.3, p.403-411, July 1980
	Paolo Atzeni , Edward P. F. Chan, Efficient optimization of simple chase join expressions, ACM Transactions on Database Systems (TODS), v.14 n.2, p.212-230, June 1989
	Rakesh M. Verma, A theory of using history for equational systems with applications, Journal of the ACM (JACM), v.42 n.5, p.984-1020, Sept. 1995
	Jiazhen Cai , Robert A. Paige, Look ma, no hashing, and no arrays neither, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.143-154, January 21-23, 1991, Orlando, Florida, United States
	Stavros S. Cosmadakis , Paris C. Kanellakis , Moshe Y. Vardi, Polynomial-time implication problems for unary inclusion dependencies, Journal of the ACM (JACM), v.37 n.1, p.15-46, Jan. 1990
	Jean Gallier , Paliath Narendran , Stan Raatz , Wayne Snyder, Theorem proving using equational matings and rigid E-unification, Journal of the ACM (JACM), v.39 n.2, p.377-430, April 1992
	Christoph Weidenbach, Combining superposition, sorts and splitting, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
	J. A. van Hulzen, Breuer's grow factor algorithm in computer algebra, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.100-104, August 05-07, 1981, Snowbird, Utah, United States
	Seth Hallem , Benjamin Chelf , Yichen Xie , Dawson Engler, A system and language for building system-specific, static analyses, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Harald Ganzinger, Efficient deductive methods for program analysis, ACM SIGPLAN Notices, v.36 n.3, p.102-103, March 2001
	Seymour Ginsburg , Sami Mohammed Zaiddan, Properties of functional-dependency families, Journal of the ACM (JACM), v.29 n.3, p.678-698, July 1982
	K. N. Venkataraman, Decidability of the purely existential fragment of the theory of term algebras, Journal of the ACM (JACM), v.34 n.2, p.492-510, April 1987
	David A. McAllester, Automatic recognition of tractability in inference relations, Journal of the ACM (JACM), v.40 n.2, p.284-303, April 1993
	Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982
	Greg Nelson , Derek C. Oppen, Simplification by Cooperating Decision Procedures, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.245-257, Oct. 1979
	Zheng Zhou , Wayne Burleson, Equivalence checking of datapaths based on canonical arithmetic expressions, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.546-551, June 12-16, 1995, San Francisco, California, United States
	Matthias Jarke , Jim Clifford , Yannis Vassiliou, An optimizing prolog front-end to a relational query system, ACM SIGMOD Record, v.14 n.2, June 1984
	Alessandro Armando , Silvio Ranise , Michaël Rusinowitch, A rewriting approach to satisfiability procedures, Information and Computation, v.183 n.2, p.140-164, 15 June 2003
	Jochen Burghardt, E-generalization using grammars, Artificial Intelligence, v.165 n.1, p.1-35, June 2005
	Guillem Godoy , Robert Nieuwenhuis , Ashish Tiwari, Classes of term rewrite systems with polynomial confluence problems, ACM Transactions on Computational Logic (TOCL), v.5 n.2, p.321-331, April 2004
	Yichen Xie , Dawson Engler, Using redundancies to find errors, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
	Wuu Yang , Susan Horwitz , Thomas Reps, A program integration algorithm that accommodates semantics-preserving transformations, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.3, p.310-354, July 1992
	M. F. van Bommel , G. E. Weddell, Reasoning About Equations and Functional Dependencies on Complex Objects, IEEE Transactions on Knowledge and Data Engineering, v.6 n.3, p.455-469, June 1994
	Grant E. Weddell, Reasoning about functional dependencies generalized for semantic data models, ACM Transactions on Database Systems (TODS), v.17 n.1, p.32-64, March 1992
	Marc H. Graham , Moshe Y. Vardi, On the complexity and axiomatizability of consistent database states, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada
	Rakesh Verma, Algorithms and reductions for rewriting problems. II, Information Processing Letters, v.84 n.4, p.227-233, 30 November 2002
	Marc H. Graham, Functions in databases, ACM Transactions on Database Systems (TODS), v.8 n.1, p.81-109, March 1983
	Adam Webber, Optimization of functional programs by grammar thinning, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.293-330, March 1995
	Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979
	Robert L. Constable , Scott D. Johnson, A PL/CV precis, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.7-20, January 29-31, 1979, San Antonio, Texas
	David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005
	Søren Debois, Imperative program optimization by partial evaluation, Proceedings of the 2004 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.113-122, August 24-25, 2004, Verona, Italy
	Abdelwahab Hamou-Lhadj , Timothy C. Lethbridge, A survey of trace exploration tools and techniques, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.42-55, October 04-07, 2004, Markham, Ontario, Canada
	Yichen Xie , Dawson Engler, Using redundancies to find errors, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
	Robert A. Mueller , Joseph Varghese , Vicki H. Allan, Global methods in the flow graph approach to retargetable microcode generation, ACM SIGMICRO Newsletter, v.15 n.4, p.275-284, Dec. 1984
	Mohammad Ali Ghodrat , Tony Givargis , Alex Nicolau, Equivalence checking of arithmetic expressions using fast evaluation, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA
	Rajeev Joshi , Greg Nelson , Keith Randall, Denali: a goal-directed superoptimizer, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Leo Bachmair , Ashish Tiwari , Laurent Vigneron, Abstract Congruence Closure, Journal of Automated Reasoning, v.31 n.2, p.129-168, 2003
	Jan Chomicki , Tomasz Imieliński, Relational specifications of infinite query answers, ACM SIGMOD Record, v.18 n.2, p.174-183, June 1989
	Douglas Gregor , Jaakko Järvi , Jeremy Siek , Bjarne Stroustrup , Gabriel Dos Reis , Andrew Lumsdaine, Concepts: linguistic support for generic programming in C++, ACM SIGPLAN Notices, v.41 n.10, October 2006
	Robert Nieuwenhuis , Albert Oliveras , Cesare Tinelli, Solving SAT and SAT Modulo Theories: From an abstract Davis--Putnam--Logemann--Loveland procedure to DPLL(T), Journal of the ACM (JACM), v.53 n.6, p.937-977, November 2006
	Ting Zhang , Henny B. Sipma , Zohar Manna, Decision procedures for term algebras with integer constraints, Information and Computation, v.204 n.10, p.1526-1574, October 2006
	Rajeev Joshi , Greg Nelson , Yunhong Zhou, Denali: A practical algorithm for generating optimal code, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.6, p.967-989, November 2006
	Steven Eker , Narciso Martí-Oliet , José Meseguer , Alberto Verdejo, Deduction, Strategies, and Rewriting, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.11, p.3-25, July, 2007
	Robert Nieuwenhuis , Albert Oliveras, Fast congruence closure and extensions, Information and Computation, v.205 n.4, p.557-580, April, 2007
	Yannis Vassiliou, Functional dependencies and incomplete information, Proceedings of the sixth international conference on Very Large Data Bases, p.260-269, October 01-03, 1980, Montreal, Quebec, Canada
	Yevgen Voronenko , Markus Püschel, Multiplierless multiple constant multiplication, ACM Transactions on Algorithms (TALG), v.3 n.2, p.11-es, May 2007
	Rakesh M. Verma , Michael Rusinowitch , Denis Lugiez, Algorithms and Reductions for Rewriting Problems, Fundamenta Informaticae, v.46 n.3, p.257-276, August 2001
	Sylvain Conchon , Evelyne Contejean , Johannes Kanig , Stéphane Lescuyer, CC(X): Semantic Combination of Congruence Closure with Solvable Theories, Electronic Notes in Theoretical Computer Science (ENTCS), v.198 n.2, p.51-69, May, 2008
	Alessandro Armando , Maria Paola Bonacina , Silvio Ranise , Stephan Schulz, New results on rewrite-based satisfiability procedures, ACM Transactions on Computational Logic (TOCL), v.10 n.1, p.1-51, January 2009
	Rakesh Verma, Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems, Fundamenta Informaticae, v.92 n.1-2, p.145-168, January 2009
	Rakesh M. Verma, Unique normal forms and confluence of rewrite systems: persistence, Proceedings of the 14th international joint conference on Artificial intelligence, p.362-368, August 20-25, 1995, Montreal, Quebec, Canada