Syntax-directed, semantics-supported program synthesis

摘要

A number of strategies for the synthesis of algorithms from a given input-output specification of a problem are presented which are centered around a few basic principles. It has been verified for more than ten different algorithms that their uniform application in all cases results in a successful deductive synthesis. Many of these deductions are presented here including those of a spanning-tree algorithm, a graph-circuits algorithm, a finding the ith smallest element algorithm, and a linear (string) pattern-matching algorithm.