https://www.mdu.se/

Efficient Bottom-up Evaluation of Magic Programs 2000 (English)Student thesis

Abstract [en]

Bottom-up evaluation of logic programs is a well-known technique typically used in deductive databases and in abstract interpretation. In these applications, bottom-up evaluation is often preceded by a transformation of the program into a so called "magic program". The problem addressed in this report is how to optimize bottom-up evaluation for this special case. The report presents a new bottom-up evaluation method for magic programs, based on a combination of two known optimizations, induced magic and the use of strongly connected components. Induced magic takes advantage of the structure of magic programs to avoid some recomputation. Magic programs are characterized by clause bodies with a high degree of overlapping, and the method uses this information to avoid some recomputation. Using strongly connected components, the program is statically divided into partitions that can be handled separately. This results in smaller data structures, decreasing the computation time. The report discusses the problem of combining these two methods, and presents a method where the basic ideas of both are used. It also outlines an efficient implementation of the method. Finally, it describes a system where bottom-up evaluation is used to compute regular approximations of magic programs. It is shown that the method can be incorporated into this system, and that this results in improved performance for the benchmark programs.

Place, publisher, year, edition, pages

2000.

Identifiers

URN: urn:nbn:se:mdh:diva-10906OAI: oai:DiVA.org:mdh-10906DiVA, id: diva2:369245

Available from: 2010-11-10 Created: 2010-11-10

Open Access in DiVA

No full text in DiVA

Search in DiVA

By author/editor

Carlson, Jan

By organisation

School of Innovation, Design and Engineering

Search outside of DiVA

GoogleGoogle ScholarTotal: 92 hits