
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Learning of Finite Unions of Tree Patterns with Internal Structured Variables from Queries
Satoshi MATSUMOTO Takayoshi SHOUDAI Tomoyuki UCHIDA Tetsuhiro MIYAHARA Yusuke SUZUKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E91D
No.2
pp.222230 Publication Date: 2008/02/01 Online ISSN: 17451361
DOI: 10.1093/ietisy/e91d.2.222 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Algorithmic Learning Theory Keyword: exact learning, computational learning theory, finite union of tree pattern languages,
Full Text: PDF>>
Summary:
A linear term tree is defined as an edgelabeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edgelabeled 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 edgelabeled rooted ordered trees for all variables in t. Moreover, for a finite set S of linear term trees, we define L(S)=∪_{t∈S} 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 2mn^{2} 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.

