A Class of Prolog Programs with Non-Linear Outputs Inferable from Positive Data
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].
Cite
Text
Rao. "A Class of Prolog Programs with Non-Linear Outputs Inferable from Positive Data." International Conference on Algorithmic Learning Theory, 2005. doi:10.1007/11564089_25Markdown
[Rao. "A Class of Prolog Programs with Non-Linear Outputs Inferable from Positive Data." International Conference on Algorithmic Learning Theory, 2005.](https://mlanthology.org/alt/2005/rao2005alt-class/) doi:10.1007/11564089_25BibTeX
@inproceedings{rao2005alt-class,
title = {{A Class of Prolog Programs with Non-Linear Outputs Inferable from Positive Data}},
author = {Rao, M. R. K. Krishna},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2005},
pages = {312-326},
doi = {10.1007/11564089_25},
url = {https://mlanthology.org/alt/2005/rao2005alt-class/}
}