The programming by example approach of [1]} learns programs from
input-output examples and relies on lightweight interaction to refine the
specification of programs to be synthesised. The approach has further been
extended in [2]} with machine learning, allowing to learn
programs from just one (or even none) input-output example by using a simple
supervised learning setup. Program synthesis from input-output examples is shown
to be successful for recursive programs [3]}, yet synthesising
loops and handling non-linear arithmetic is not yet supported by this
line of research. Our work precisely
characterises the solution space of all loops to be synthesised by a system of
algebraic recurrences and does not use statistical models supporting
machine learning.
