Synthesis of Conversion Rules by Expanding Logic Programs

Hiroshi Mabuchi, Kiyoshi Akama, Hidekatsu Koike

In Proc. of the International Workshop on Functional and (Constraint) Logic Programming (WFLP 2001) , Report No. 2017, University of Kiel


Each of knowledge representations has been shown to be superior for certain types of problems. However, in some cases a problem can not be solved effectively and automatically in only the space of a certain knowledge representation. We therefore consider how to solve such problems effectively and automatically. As a solution, we propose in this paper a natural and efficient method for solving a problem by expanding the space using the characteristics of the space in which the problem can not be solved. We deal with the synthesis of conversion rules that simplify a logical circuit as a concrete problem, and by comparing the synthesis of conversion rules in the space before expansion (space of logic programs) with that in the space after expansion, we show that expansion of logic programs is efficient for synthesis of conversion rules. The synthesis of conversion rules requires a new conversion rule (i.e., synthesis rule), which is obtained by combining two or more existing successive conversion rules to achieve a new conversion from one state to another. In the space after expansion, various data structures, including strings and multisets as well as terms, can be treated. The synthesis of conversion rules is performed by equivalent transformation. Equivalent transformation is the conversion of a program into another equivalent program. The expansion of logic programs is performed by applying equivalent transformation rule and enables a useful synthesis rule for problem solving to be obtained efficiently and automatically and at a low cost.