Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries

Satoshi MATSUMOTO  Takayoshi SHOUDAI  Tomoyuki UCHIDA  Tetsuhiro MIYAHARA  Yusuke SUZUKI  

IEICE TRANSACTIONS on Information and Systems   Vol.E91-D   No.2   pp.222-230
Publication Date: 2008/02/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e91-d.2.222
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Algorithmic Learning Theory
exact learning,  computational learning theory,  finite union of tree pattern languages,  

Full Text: PDF>>
Buy this Article

A linear term tree is defined as an edge-labeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edge-labeled rooted ordered trees. We consider the polynomial time learnability of finite unions of linear term trees in the exact learning model formalized by Angluin. The language L(t) of a linear term tree t is the set of all trees obtained from t by substituting arbitrary edge-labeled rooted ordered trees for all variables in t. Moreover, for a finite set S of linear term trees, we define L(S)=∪tS L(t). A target of learning, denoted by T*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set T* of m linear term trees (m ≥ 0), we present a query learning algorithm which exactly identifies T* in polynomial time using at most 2mn2 Restricted Subset queries and at most m+1 Equivalence queries, where n is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using Restricted Equivalence, Membership and Subset queries.