%0 Journal Article %1 Kitzelmann07a %A Kitzelmann, Emanuel %A Schmid, Ute %B Proceedings of the 7th International Workshop on Rule Based Programming (RULE 2006) %D 2007 %J Electronic Notes in Theoretical Computer Science %K 2007 article automatic_programming constructor_systems functional_programming igor2 induction inductive inductive_inference inductive_program_synthesis inductive_programming myown programming published rule-based_programming %N 1 %P 49--63 %T Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities %U http://dx.doi.org/10.1016/j.entcs.2006.11.015 %V 174 %X We present a technique for inducing functional programs from few, well chosen input/output-examples (I/O-examples). Potential applications for automatic program or algorithm induction are to enable end users to create their own simple programs, to assist professional programmers, or to automatically invent completely new and efficient algorithms. In our approach, functional programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples for a target function to be implemented are a set of pairs of terms (F(i_i),o_i) meaning that F(i_i)---denoting application of function F to input i_i---is rewritten to o_i by a CS implementing the function F. Induction is based on detecting syntactic regularities between example terms. In this paper we present theoretical results and describe an algorithm for inducing CSs over arbitrary signatures/data types which consist of one function defined by an arbitrary number of rules with an arbitrary number of non-nested recursive calls in each rule. Moreover, we present empirical results based on a prototypical implementation.

@article{Kitzelmann07a, abstract = {We present a technique for inducing functional programs from few, well chosen input/output-examples (I/O-examples). Potential applications for automatic program or algorithm induction are to enable end users to create their own simple programs, to assist professional programmers, or to automatically invent completely new and efficient algorithms. In our approach, functional programs are represented as constructor term rewriting systems (CSs) containing recursive rules. I/O-examples for a target function to be implemented are a set of pairs of terms (F(i_i),o_i) meaning that F(i_i)---denoting application of function F to input i_i---is rewritten to o_i by a CS implementing the function F. Induction is based on detecting syntactic regularities between example terms. In this paper we present theoretical results and describe an algorithm for inducing CSs over arbitrary signatures/data types which consist of one function defined by an arbitrary number of rules with an arbitrary number of non-nested recursive calls in each rule. Moreover, we present empirical results based on a prototypical implementation.}, added-at = {2007-10-17T15:28:39.000+0200}, author = {Kitzelmann, Emanuel and Schmid, Ute}, biburl = {https://www.bibsonomy.org/bibtex/20f49c7d956f306d32d63b18f5a106022/mh}, booktitle = {Proceedings of the 7th International Workshop on Rule Based Programming (RULE 2006)}, description = {ScienceDirect - Electronic Notes in Theoretical Computer Science : Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities}, interhash = {2dcd4314ec132af22225ada9f0813473}, intrahash = {0f49c7d956f306d32d63b18f5a106022}, journal = {Electronic Notes in Theoretical Computer Science}, keywords = {2007 article automatic_programming constructor_systems functional_programming igor2 induction inductive inductive_inference inductive_program_synthesis inductive_programming myown programming published rule-based_programming}, month = {#apr#}, number = 1, pages = {49--63}, timestamp = {2007-10-17T15:28:41.000+0200}, title = {Inducing Constructor Systems from Example-Terms by Detecting Syntactical Regularities}, url = {http://dx.doi.org/10.1016/j.entcs.2006.11.015}, volume = 174, year = 2007 }