Abstract Interpretation: A Kind of Magic
1995 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 142, no 1, 125-138 p.Article in journal (Refereed) Published
Magic sets and, more recently, magic templates have been used in the field of deductive databases to facilitate efficient bottom-up evaluation of database queries. Roughly speaking a top-down computation of a definite logic program is simulated by first transforming the program and then executing the new program bottom-up. In this paper we give a new and very simple proof that this approach is equivalent to the collecting interpretation of the abstract interpretation framework for logic programs of Mellish. As a side-effect we are also able to show that “bottom-up” abstract interpretation based on the magic templates transformation is equally powerful as Mellish's abstract interpretation framework, but less powerful than other (more precise) abstract interpretation frameworks.
Place, publisher, year, edition, pages
Elsevier , 1995. Vol. 142, no 1, 125-138 p.
IdentifiersURN: urn:nbn:se:liu:diva-67122DOI: http://dx.doi.org/10.1016/0304-3975(94)00223-6OAI: oai:DiVA.org:liu-67122DiVA: diva2:407558