Two New Operators for IGOR2 to Increase Synthesis Efficiency

TitleTwo New Operators for IGOR2 to Increase Synthesis Efficiency
Publication TypeConference Paper
Year of Publication2011
AuthorsKitzelmann, E.
Page(s)49-61
Other Numbers3217
Abstract

Inductive program synthesis addresses the problem of automatically generating computer programs from incomplete specifications such as input/output examples. Potential applications range from automated software development to end-user programming to autonomousintelligent agents that learn from experience or observation.We present arecent version of the domain-independent algorithm Igor2 for the inductive synthesis of recursive functional programs, represented as rewriting rules. Igor2 combines classical analytical methods, that detect recursion by matching I/O examples, with search in program spaces as applied by recent generate-and-test methods; thereby widening the classof programs that are synthesizable in reasonable time. In particular, wepresent two recent improvements over an earlier Igor2 version whichsignificantly increase the efficiency of the synthesis. Functions that werenot inducible in several minutes are now induced in several seconds. Ithas already been shown that an earlier version of Igor2 outperformsother recent systems on several problems. In the empirical evaluationhere, we show the significance of the improved synthesis operators bymeans of more complex problems, most of which were not tractable forIgor2 until now.

Acknowledgment

This work was partially funded by the Deutscher Akademischer Austausch Diesnst (DAAD) through a postdoctoral fellowship.

URLhttp://www.icsi.berkeley.edu/pubs/ai/Kitzelmann2011a.pdf
Bibliographic Notes

Proceedings of the Fourth International Workshop on Approaches and Applications of Inductive Programming (AAIP 2011), pp. 49-61, Odense, Denmark

Abbreviated Authors

E. Kitzelmann

ICSI Research Group

AI

ICSI Publication Type

Article in conference proceedings