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
Abstract
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.