Skip Navigation

IEICE Transactions on Information and Systems 2008 E91-D(2):222-230; doi:10.1093/ietisy/e91-d.2.222
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Request Permissions
Google Scholar
Right arrow Articles by MATSUMOTO, S.
Right arrow Articles by SUZUKI, Y.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Special Section on Foundations of Computer Science -- Papers -- Algorithmic Learning Theory

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

Satoshi MATSUMOTO1, Takayoshi SHOUDAI2, Tomoyuki UCHIDA3, Tetsuhiro MIYAHARA3 and Yusuke SUZUKI3

1 The author is with the Department of Mathematical Sciences, Tokai University, Hiratsuka-shi, 259–1292 Japan. E-mail: matumoto{at}ss.u-tokai.ac.jp, 2 The author is with the Department of Informatics, Kyushu University, Fukuoka-shi, 819–0395 Japan., 3 The authors are with the Graduate School of Information Sciences, Hiroshima City University, Hiroshima-shi, 731–3194 Japan.


  Abstract

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) = {cup}tisinSL(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.

Key Words: exact learning, computational learning theory, finite union of tree pattern languages

Manuscript received March 30, 2007. Manuscript revised June 30, 2007.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.