Off-line and on-line algorithms for deducing equalities

Peter Downey; Hanan Samet; Ravi Sethi

doi:10.1145/512760.512777

Off-line and on-line algorithms for deducing equalities

Peter Downey, Hanan Samet, Ravi Sethi

Research output: Contribution to journal › Conference article › peer-review

10 Scopus citations

Abstract

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 f_j1 ≠f_j2 which must have different values. We ask if as a result, h₁=h₂, or h₁≠h₂. 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 language	English (US)
Pages (from-to)	158-170
Number of pages	13
Journal	Conference Record of the Annual ACM Symposium on Principles of Programming Languages
DOIs	https://doi.org/10.1145/512760.512777
State	Published - Jan 1 1978
Externally published	Yes
Event	5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978 - Tucson, United States Duration: Jan 23 1978 → Jan 25 1978

ASJC Scopus subject areas

Software

Access to Document

10.1145/512760.512777

Cite this

@article{24f1f24449c64fa29d7afd9907769b1d,

title = "Off-line and on-line algorithms for deducing equalities",

abstract = "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.",

author = "Peter Downey and Hanan Samet and Ravi Sethi",

note = "Publisher Copyright: {\textcopyright} 1986 ACM.; 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978 ; Conference date: 23-01-1978 Through 25-01-1978",

year = "1978",

month = jan,

day = "1",

doi = "10.1145/512760.512777",

language = "English (US)",

pages = "158--170",

journal = "Conference Record of the Annual ACM Symposium on Principles of Programming Languages",

issn = "0730-8566",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - Off-line and on-line algorithms for deducing equalities

AU - Downey, Peter

AU - Samet, Hanan

AU - Sethi, Ravi

PY - 1978/1/1

Y1 - 1978/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0018057284&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0018057284&partnerID=8YFLogxK

U2 - 10.1145/512760.512777

DO - 10.1145/512760.512777

M3 - Conference article

AN - SCOPUS:0018057284

SN - 0730-8566

SP - 158

EP - 170

JO - Conference Record of the Annual ACM Symposium on Principles of Programming Languages

JF - Conference Record of the Annual ACM Symposium on Principles of Programming Languages

T2 - 5th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1978

Y2 - 23 January 1978 through 25 January 1978

ER -

Off-line and on-line algorithms for deducing equalities

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this