Variations on the Common Subexpression Problem

Peter J. Downey, Ravi Sethi, Robert Endre Tarjan

Research output: Contribution to journalArticle

213 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)758-771
Number of pages14
JournalJournal of the ACM (JACM)
Volume27
Issue number4
DOIs
StatePublished - Oct 1 1980
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Variations on the Common Subexpression Problem'. Together they form a unique fingerprint.

  • Cite this