Variations on the Common Subexpression Problem
Peter J. Downey, Ravi Sethi, Robert Endre Tarjan · Journal of the ACM · 1980
Let G be a directed graph such that for each vertex v in G, the successors of v are ordered Let C be any equivalence relation on the vertices of G.The congruence closure C* of C is the finest equivalence relation containing C and such that any two vertices having corresponding successors equivalent under C* are themselves equivalent under C* Efficient algorithms are described for computing congruence closures in the general case and in the following two special cases.0) G under C* is acyclic, and (it) G is acychc and C identifies a single pair of vertices.The use of these algorithms to test expression eqmvalence (a problem central to program verification) and to test losslessness of joins in relational databases is described KEY WORDS AND PHRASES common subexpresslon, congruence closure, decision procedure, expression equivalence, graph algorithm, lossless join, relational database, theory of equality, unification, uniform word problem CR CATEGORIES 4 12, 4.33, 4 34, 5.24, 5 25, 5 32
Cited by 353 works. doi:10.1145/322217.322228 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- Efficiency of a Good But Not Linear Set Union Algorithm
- The art of computer programming. Vol.1: Fundamental algorithms
- Algorithmic Aspects of Vertex Elimination on Graphs
- Programming languages and their compilers: Preliminary notes
- Storing a sparse table
- Fast Decision Procedures Based on Congruence Closure
- Linear unification