Efficient Inductive Inference of Primitive Prologs from Positive Data
Abstract
This paper is concerned with the problem of efficient inductive inference of primitive Prologs from only positive data. The class of primitive Prologs is a proper subclass of one of linear Prologs that is known to be inferable from only positive data. In this paper, we discuss on the consistent and conservative polynomial update time inferability of the subclass. We give a consistent and conservative polynomial update time inference algorithm that, when it is given the base case of the target program as a hint, identifies the subclass in the limit. Furthermore, we give a consistent but not conservative polynomial update time inference algorithm for the subclass using a 2-mmg (minimal multiple generalization) algorithm. The notion of 2-mmg is a natural extension of Plotkin's least generalization. The second inference algorithm uses the 2-mmg algorithm to infer the heads of clauses in a target program.
Cite
Text
Ishizaka et al. "Efficient Inductive Inference of Primitive Prologs from Positive Data." International Conference on Algorithmic Learning Theory, 1992. doi:10.1007/3-540-57369-0_34Markdown
[Ishizaka et al. "Efficient Inductive Inference of Primitive Prologs from Positive Data." International Conference on Algorithmic Learning Theory, 1992.](https://mlanthology.org/alt/1992/ishizaka1992alt-efficient/) doi:10.1007/3-540-57369-0_34BibTeX
@inproceedings{ishizaka1992alt-efficient,
title = {{Efficient Inductive Inference of Primitive Prologs from Positive Data}},
author = {Ishizaka, Hiroki and Arimura, Hiroki and Shinohara, Takeshi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1992},
pages = {135-146},
doi = {10.1007/3-540-57369-0_34},
url = {https://mlanthology.org/alt/1992/ishizaka1992alt-efficient/}
}