Polynomial-Time Inference of Unions of Tree Pattern Languages
Abstract
In this paper we consider the polynomial time inferability from positive data for unions of two tree pattern languages. A tree pattern is a structured pattern known as a term in logic programming and term rewriting systems, and a tree pattern language is the set of all ground instances of a tree pattern. We present a polynomial time algorithm to find a minimal union of two tree pattern languages containing given examples. Our algorithm can be considered as a natural extension of Plotkin's least generalization algorithm, which finds a minimal single tree pattern language. By using this algorithm we can realize a polynomial time inference machine for unions of two tree pattern languages from positive data.
Cite
Text
Arimura et al. "Polynomial-Time Inference of Unions of Tree Pattern Languages." International Conference on Algorithmic Learning Theory, 1991.Markdown
[Arimura et al. "Polynomial-Time Inference of Unions of Tree Pattern Languages." International Conference on Algorithmic Learning Theory, 1991.](https://mlanthology.org/alt/1991/arimura1991alt-polynomialtime/)BibTeX
@inproceedings{arimura1991alt-polynomialtime,
title = {{Polynomial-Time Inference of Unions of Tree Pattern Languages}},
author = {Arimura, Hiroki and Shinohara, Takeshi and Otsuki, Setsuko},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1991},
pages = {105-114},
url = {https://mlanthology.org/alt/1991/arimura1991alt-polynomialtime/}
}