Technical Report No. 121 - Abstract

S. Schroedl, S. Edelkamp
Inferring Flow of Control in Program Synthesis by Example

We present a supervised, interactive learning technique that infers control structures of computer programs from user-demonstrated traces. A two-stage process is applied: first, a minimal deterministic finite automaton (DFA) M labeled by the instructions of the program is learned from a set of example traces and membership queries to the user. It accepts all prefixes of traces of the target program. The number of queries is bounded by O(k|M|), with k being the total number of instructions in the initial example traces. In the second step we parse this automaton into a high-level programming language in O(|M|^2) steps, replacing jumps by conditional control structures.