Synthesizing minimal programs from traces of observable behaviour

Abstract

Automatic synthesis of non-recursive flowchart programs from traces of observable behaviour is investigated. Our program synthesis algorithm described here can be applied to sets of sequences of stores yielding minimal programs being capable of reproducing these sequences. An efficient decision procedure for solvability of program synthesis problems is presented. An extension of PA admits four different types of input traces. For all four types program synthesis remains NP-complete even under various constraints.