Speedup of Logic Programs by Binarization and Partial Deduction

Title: Speedup of Logic Programs by Binarization and Partial Deduction

Research Question: Can binarization and partial deduction improve the computational behavior of logic programs?

Methodology: The authors propose a transformation of logic programs to binary logic programs. This transformation involves two steps: binarization and partial deduction. Binarization transforms the original program into a binary program, which contains only clauses with at most one atom in the body. Partial deduction then specializes the binary program by applying a series of LD-resolutions.

Results: The authors introduce the class of B-stratified logic programs, which are programs that can be transformed into binary programs without introducing new continuation variables through binarization. They prove that for B-stratified programs, binarization and partial deduction result in programs with better computational behavior.

Implications: This research suggests that binarization and partial deduction can be used to improve the performance of logic programs, especially for B-stratified programs. The authors also compare their approach with other related transformations and show that it produces programs with identical computational behavior.

In conclusion, the research provides a practical method for improving the efficiency of logic programs by transforming them into binary programs and applying partial deduction. The effectiveness of this method is particularly promising for B-stratified programs.

Link to Article: https://arxiv.org/abs/0312026v1 Authors: arXiv ID: 0312026v1