Polynomial Time Inference of Unions of Two Tree Pattern Languages

Hiroki ARIMURA  Takeshi SHINOHARA  Setsuko OTSUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.4   pp.426-434
Publication Date: 1992/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Issue on Algorithmic Learning Theory)
Category: 
Keyword: 
inductive inference,  learning,  pattern language,  polynomial time algorithm,  inference from positive data,  

Full Text: PDF(855.9KB)
>>Buy this Article


Summary: 
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 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 consistent and conservative polynomial time inference machine that identifies unions of two tree pattern languages from positive data in the limit.