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

Access this Article

Search 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 <i>L</i>(<i>t</i>) of a linear term tree <i>t</i> is the set of all trees obtained from <i>t</i> by substituting arbitrary edge-labeled rooted ordered trees for all variables in <i>t</i>. Moreover, for a finite set <i>S</i> of linear term trees, we define <i>L</i>(<i>S</i>)=∪<sub><i>t</i>∈<i>S</i></sub><i>L</i>(<i>t</i>). A target of learning, denoted by <i>T</i>*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set <i>T</i>* of <i>m</i> linear term trees (<i>m</i>≥0), we present a query learning algorithm which exactly identifies <i>T</i>* in polynomial time using at most 2<i>mn</i><sup>2</sup> <i>Restricted Subset</i> queries and at most <i>m</i>+1 <i>Equivalence</i> queries, where <i>n</i> is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using <i>Restricted Equivalence, Membership</i> and <i>Subset</i> queries.


  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems 91(2), 222-230, 2008-02-01

    The Institute of Electronics, Information and Communication Engineers

References:  18

Cited by:  3


  • NII Article ID (NAID)
  • Text Lang
  • Article Type
    Journal Article
  • ISSN
  • Data Source
    CJP  CJPref  J-STAGE 
Page Top