mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient Bottom-up Evaluation of Magic Programs
Mälardalen University, School of Innovation, Design and Engineering.
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: diva2:369245
Available from: 2010-11-10 Created: 2010-11-10

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Carlson, Jan
By organisation
School of Innovation, Design and Engineering

Search outside of DiVA

GoogleGoogle Scholar

Total: 45 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf