Off-line and on-line algorithms for deducing equalities

Peter Downey, Hanan Samet, Ravi Sethi

Research output: Contribution to journalConference articlepeer-review

10 Scopus citations


The classical common subexpression problem in program optimization is the detection of identical subexpressions. Suppose we have some extra information and are given pairs of expressions e. =e.. which must have the same value, and expressions fj1 ≠fj2 which must have different values. We ask if as a result, h1=h2, or h1≠h2. This has been called the uniform word problem for finitely presented algebras, and has application in theoremproving and code optimization. We show that such questions can be answered in O(nlogn) time, where n is the number of nodes in a graph representation of all relevant expressions. A linear time algorithm for detecting common subexpressions is derived. Algorithms which process equalities, inequalities and deductions on-line are discussed.

Original languageEnglish (US)
Pages (from-to)158-170
Number of pages13
JournalConference Record of the Annual ACM Symposium on Principles of Programming Languages
StatePublished - Jan 1 1978
Event5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978 - Tucson, United States
Duration: Jan 23 1978Jan 25 1978

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Off-line and on-line algorithms for deducing equalities'. Together they form a unique fingerprint.

Cite this