A Linear Reduction Model for Parallel Prolog System
Wei Zhang, Shenggui Hong · 2019
As one of the most influential artificial intelligence programming languages, Prolog can naturally express human’s thinking and reasoning process. Thus, it has been widely applied in mechanical theorem proving, robot, intelligent planning, etc. However, the reasoning process of traditional Prolog is inefficient since it requires a lot of backtracking. This paper presents a novel linear reduction model different from the previous prolog derivation--generalized and/or graph search model, which can clearly represent variable (binding) constraints, so no backtracking is needed. In this model, a successful derivation of Prolog corresponds to a solution sub-graph of the corresponding generalized and/or graph. Therefore, the prolog reasoning is transformed into a searching process without backtracking, which can be parallel executed and greatly improves the efficiency of the prolog deduction. Furthermore, we discuss the transformation of artificial intelligence heuristic search technology, which is mature in both theory and practice, to Prolog reasoning, and obtain a more effective algorithm.