Efficient backward execution in AND/OR process model (Q1114389)

A method of generating n-tuples for a clause with n variables as its argument under the AND/OR process model [\textit{J. Conery}, The AND/OR process model for parallel interpretation of logic programs, Ph. D. Diss., Univ. California at Urvine (1983)] of logic programs is considered. The AND/OR process model uses the nested loop model for it, which incurs much inefficiencies because it does not consider the relationship between literals. The improvement based on this point is made from static analysis of the data dependency graph which represents the relationship between literals in a clause. It is shown that our improved method for generating tuples is better than the AND/OR process model. Adoption of the improved method makes multiple failure situation handled more efficiently. We also show that several backtrack literals can be found for multiple failures by analysing the sources of failures when the improved method is used for generating tuples. Our method is illustrated by several examples.