Programmsynthese aus Beispielsfolgen

Abstract

Automatic program synthesis from example computations is investigated. Four kinds of instruction and store description sequences are distinguished; for each the problem of program synthesis is shown to be NP—complete. NP-completeness is shown also for various restricted subclasses of the general problem as well as for the synthesis of Turing machines and Mealy automatons from traces of their behavior. A decision procedure for solvability of program synthesis problems is presented. A universal program synthesis algorithm applicable to different kinds df example computations and yielding minimal programs is designed and verified. Due to its representation methods and extensive pruning techniques it solves a large class of program synthesis problems efficiently.