Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The undecidability of aliasing
Ramalingam G. ACM Transactions on Programming Languages and Systems16 (5):1467-1471,1994.Type:Article
Date Reviewed: Aug 1 1995

Common static program analyses such as reaching-definition analysis and live-variables analysis require alias information. Two names (L-valued expressions) are said to alias each other at a particular point during program execution if both may, or must, have the same value. Landi [1] recently established that “may” and “must” alias problems are undecidable for languages that permit “if” statements, loops, dynamic storage, and recursive data structures. Ramalingam presents a simpler and very elegant proof of the same result. The approach taken is to reduce Post’s Correspondence Problem (PCP), which is undecidable, to the “may” and “must” alias problems. The proof is supported by a program example in C. If you are working in the field of static program analysis, be sure to take a look at this short and easy-to-read paper.

Reviewer:  D. B. Lange Review #: CR118859 (9508-0606)
1) Landi, W. Undecidability of static analysis. ACM Lett. Program. Lang. Syst. 1, 4 (Dec. 1992), 323–337.
Bookmark and Share
 
Optimization (D.3.4 ... )
 
 
Compilers (D.3.4 ... )
 
 
Computability Theory (F.4.1 ... )
 
 
Decision Problems (F.4.3 ... )
 
 
Procedures, Functions, And Subroutines (D.3.3 ... )
 
 
Formal Languages (F.4.3 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Optimization": Date
Finite constants
Steffen B., Knoop J. Theoretical Computer Science 80(2): 303-318, 1991. Type: Article
May 1 1992
Optimizing schemes for structured programming language processors
Tsuji T., Ellis Horwood, Upper Saddle River, NJ, 1990. Type: Book (9780138551230)
Apr 1 1992
Optimizing compilers for parallel computers (videotape)
Allen F., University Video Communications, Stanford, CA, 1991. Type: Book
Aug 1 1993
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy