TY - JOUR
T1 - On the Complexity of Dataflow Analysis of Logic Programs
AU - Debray, Saumya K.
PY - 1995/1/3
Y1 - 1995/1/3
N2 - It is widely held that there is a correlation between complexity and precision in dataflow analysis, in the sense that the more precise an analysis algorithm, the more computationally expensive it must be. The details of this relationship, however, appear to not have been explored extensively. This article reports some results on this correlation in the context of logic programs. A formal notion of the “precision” of an analysis algorithm is proposed, and this is used to characterize the worst-case computational complexity of a number of dataflow analyses with different degrees of precision. While this article considers the analysis of logic programs, the technique proposed, namely the use of “exactness sets” to study relationships between complexity and precision of analyses, is not specific to logic programming in any way, and is equally applicable to flow analyses of other language families.
AB - It is widely held that there is a correlation between complexity and precision in dataflow analysis, in the sense that the more precise an analysis algorithm, the more computationally expensive it must be. The details of this relationship, however, appear to not have been explored extensively. This article reports some results on this correlation in the context of logic programs. A formal notion of the “precision” of an analysis algorithm is proposed, and this is used to characterize the worst-case computational complexity of a number of dataflow analyses with different degrees of precision. While this article considers the analysis of logic programs, the technique proposed, namely the use of “exactness sets” to study relationships between complexity and precision of analyses, is not specific to logic programming in any way, and is equally applicable to flow analyses of other language families.
KW - Complexity
KW - Prolog
KW - program analysis
UR - http://www.scopus.com/inward/record.url?scp=0029273133&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029273133&partnerID=8YFLogxK
U2 - 10.1145/201059.201068
DO - 10.1145/201059.201068
M3 - Article
AN - SCOPUS:0029273133
SN - 0164-0925
VL - 17
SP - 331
EP - 365
JO - ACM Transactions on Programming Languages and Systems (TOPLAS)
JF - ACM Transactions on Programming Languages and Systems (TOPLAS)
IS - 2
ER -