Polynomial Time Inference of a Subclass of Context-Free Transformations
Abstract
This paper deals with a class of Prolog programs, called context-free term transformations (CTF). We present a polynomial time algorithm to identify a subclass of CFT, whose program consists of at most two clauses, from positive data; The algorithm uses 2-mmg (2-minimal multiple generalization) algorithm, which is natural extension of Plotkin's least generalization algorithm, to reconstruct the pair of heads of the unknown program. Using this algorithm, we show the consistent and conservative polynomial time identifiability of the class of tree languages defined by CFTFBuniq together with tree languages defined by pairs of two tree patterns, both of which are proper subclasses of CFT, in the limit from positive data.
Cite
Text
Arimura et al. "Polynomial Time Inference of a Subclass of Context-Free Transformations." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130400Markdown
[Arimura et al. "Polynomial Time Inference of a Subclass of Context-Free Transformations." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/arimura1992colt-polynomial/) doi:10.1145/130385.130400BibTeX
@inproceedings{arimura1992colt-polynomial,
title = {{Polynomial Time Inference of a Subclass of Context-Free Transformations}},
author = {Arimura, Hiroki and Ishizaka, Hiroki and Shinohara, Takeshi},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {136-143},
doi = {10.1145/130385.130400},
url = {https://mlanthology.org/colt/1992/arimura1992colt-polynomial/}
}