Syntax-directed, semantics-supported program synthesis

✍ Scribed by Wolfgang Bibel

• Publisher: Elsevier Science
• Year: 1980
• Tongue: English
• Weight: 940 KB
• Volume: 14
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(80)90050-8

✦ Synopsis

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) patternmatching algorithm.