Kolloquium Montag, 30.3.15, 10 Uhr, WE5/05.013

Sebastian Boosz: Applying Anti-Unification Strategies to Matching and Generalization of Recursive Functions - Investigating a Second-order approach for Learning from Examples (Masterarbeit AI)

Programmers seldom invent completely new programs, instead they tend to adapt existing programs by analogical reasoning. After a suitable source program has been found, it is a feasible strategy to picture the execution behavior of that program for a certain input. The programmer then tries to envision the execution behavior of the desired program for the very same input. Comparing, she can draw conclusions about what both programs have in common and where the differences are located. Adapting the existing program by applying those differences appropriately, yields the desired program. In this thesis a programming by analogy approach is investigated for recursive func- tions. Based on concrete unfoldings of source and target functions, higher-order anti- unification is used to find a generalization, revealing differences between source and target. A set of heuristics was developed which is used to match and apply those dif- ferences to the source function in order to transform it into the corresponding target function. The success of the heuristics is evaluated and possible means of improvement are suggested.

Keywords: recursion, recursive functions, higher-order anti-unification, generalization, programming by analogy, learning from examples, heuristics