Studies on Foundations of Software Reuse by Inductive Inference and Analogical Reasoning

本课题旨在通过归纳推理和类比推理的方法，建立一个程序重用的理论基础。通过对已有逻辑程序的重用，我们得到了一个逻辑程序R的合成的基本过程。(1)检索一些与要合成的程序相似的程序。(2)从检索到的程序中选择一个程序P，对一些例子运行类比推理系统。(3)对成功推理中使用的P的定句进行变换，得到一个不完全程序Q。(4)从包括在(2)处失败的样本在内的一些样本中，利用从初始假设P开始的归纳推理，将期望程序Q系统化。在整个项目中，我们也得到了以下结果。对于(1)文献检索中的标引技术和力学定理证明中的抽象技术是有效的。为了在第(2)和(3)阶段中使用类比推理系统，我们发展了一种关于定句的类比推理理论，并在工程工作站中实现了该系统。我们还扩展了这一理论，以便得出合理的结论。对于(4)，我们提出了一种新的基于定分句之间双向细化的归纳推理方法，并证明了其完备性。它从一个在阶段(3)得到的中间假设开始。我们还从并行复杂性理论的角度研究了推理和推理的效率。我们得到了一个非常强大的定理，从这个定理我们可以推导出许多问题的p完备性。这意味着有很多问题不能有效地并行化。我们还提出了一种并行化一些顺序过程的算法。

This project has aimed at establishing a theoretical foundation of reuse of programs by means of inductive inference and analogical reasoning such a system.We have got the following basic process of synthesizing a logic program R by reuse of existing logic programs.(1) Retrieve some programs simielar to the one to be synthesized.(2) Select a program P out of the retrieved programs, and run the analogical reasoning system on some examples.(3) Transform the definite clauses of P used in the successful reasoning, and make an incomplete program Q.(4) Systesize the desired program Q by using inductive inference starting with the initial hypothesis P from some samples including ones failed at (2).Throughout this project, we also got the following results. AS to (1), the techniques of indexing in document retrievals and the abstration in mechanical theorem proving are found to be effective.We have developed a theory of analogical reasoning about the definite clauses for the sake of analogical reasoning system which is used in the stages (2) and (3), and implemented the system on the engineering work station. We have also extended the theory so as to derive reasonable conclusions.As to (4), we have proposed a new inductive inference method based on bidirectional refinements between definite clauses and proved its completeness.It starts with an intermediate hypothesis which is obtained at the stage (3).We have also studied the efficiency of inference and reasoning from viewpoint of parallel complexity theory. We have obtained a very powerful theorem from which we can derive P-completeness of many problems. This means there are so many problem which can not be efficiently parallelizable. We have also presented an algorithm for parallelizing some sequential procedures.