Paper Info
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 ei1=ei2 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 theorem-proving 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.
Year
DOI
Venue
1978
10.1145/512760.512777
POPL
Keywords
Field
DocType
expressions fj1,common subexpressions,code optimization,classical common subexpression problem,linear time algorithm,on-line algorithm,uniform word problem,deducing equality,program optimization,different value,identical subexpressions,expressions ei1,theorem proving,word problem,graph representation
Program optimization,Off line,Ask price,Expression (mathematics),Word problem (mathematics education),Computer science,Algorithm,Time complexity,Graph (abstract data type)
Conference
Citations 
PageRank 
References 
10
7.00
16
Authors
3
Name
Order
Citations
PageRank
Peter J. Downey1436172.07
Hanan Samet261321120.85
Ravi Sethi322811029.21