THE UNDECIDABILITY OF ALIASING

Authors
RAMALINGAM G
Citation
G. Ramalingam, THE UNDECIDABILITY OF ALIASING, ACM transactions on programming languages and systems, 16(5), 1994, pp. 1467-1471
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Software Graphycs Programming
Journal title
ACM transactions on programming languages and systems → ACNP
ISSN journal
01640925
Volume
16
Issue
5
Year of publication
1994
Pages
1467 - 1471
Database
ISI
SICI code
0164-0925(1994)16:5<1467:TUOA>2.0.ZU;2-A
Abstract
Alias analysis is a prerequisite for performing most of the common pro gram analyses such as reaching-definitions analysis or live-variables analysis. Landi [1992] recently established that it is impossible to c ompute statically precise alias information-either may-alias or must-a lias-in languages with if statements, loops, dynamic storage, and recu rsive data structures: more precisely, he showed that the may-alias re lation is not recursive,while the must-alias relation is not even recu rsively enumerable. This article presents simpler proofs of the same r esults.