A Class of Prolog Programs with Non-linear Outputs Inferable from Positive Data Author: M. R. K. Krishna Rao Source: Algorithmic Learning Theory, 16th International Conference, ALT 2005, Singapore, October 2005, Proceedings, (Sanjay Jain, Hans Ulrich Simon and Etsuji Tomita, Eds.), Lecture Notes in Artificial Intelligence 3734, pp. 312 - 326, Springer 2005. Abstract. In this paper, we study inferability of Prolog programs from positive examples alone. We define a class of Prolog programs called recursion bounded programs that can capture non-linear relationships between inputs and outputs and yet inferable from positive examples. This class is rich enough to include many programs like append, delete, insert, reverse, permute, count, listsum, listproduct, insertion-sort, quick-sort on lists, various tree traversal programs and addition, multiplication, factorial, power on natural numbers. The relation between our results and the known results is also discussed. In particular, the class of recursion bounded programs contains all the known terminating linearly-moded Prolog programs of Krishna Rao [7] and additional programs like power on natural numbers which do not belong to the class of linearly-moded programs and the class of safe programs of Martin and Sharma [12]. ©Copyright 2005, Springer