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

Access this Article

Search this Article

Abstract

The exact learning model by Angluin (1988) is a mathematical model of learning via queries in computational learning theory. A term tree is a tree pattern consisting of ordered tree structures and repeated structured variables, which occur more than once. Thus, a term tree is suited for representing common tree structures based on tree-structured data, such as HTML and XML files on the Web. In this paper, we consider the learnability of finite unions of term trees with repeated variables in the exact learning model. We present polynomial time learning algorithms for finite unions of term trees with repeated variables by using superset and restricted equivalence queries. Moreover, we show that there exists no polynomial time learning algorithm for finite unions of term trees by using restricted equivalence, membership, and subset queries. This result indicates the hardness of learning finite unions of term trees in the exact learning model.The exact learning model by Angluin (1988) is a mathematical model of learning via queries in computational learning theory. A term tree is a tree pattern consisting of ordered tree structures and repeated structured variables, which occur more than once. Thus, a term tree is suited for representing common tree structures based on tree-structured data, such as HTML and XML files on the Web. In this paper, we consider the learnability of finite unions of term trees with repeated variables in the exact learning model. We present polynomial time learning algorithms for finite unions of term trees with repeated variables by using superset and restricted equivalence queries. Moreover, we show that there exists no polynomial time learning algorithm for finite unions of term trees by using restricted equivalence, membership, and subset queries. This result indicates the hardness of learning finite unions of term trees in the exact learning model.

The exact learning model by Angluin (1988) is a mathematical model of learning via queries in computational learning theory. A term tree is a tree pattern consisting of ordered tree structures and repeated structured variables, which occur more than once. Thus, a term tree is suited for representing common tree structures based on tree-structured data, such as HTML and XML files on the Web. In this paper, we consider the learnability of finite unions of term trees with repeated variables in the exact learning model. We present polynomial time learning algorithms for finite unions of term trees with repeated variables by using superset and restricted equivalence queries. Moreover, we show that there exists no polynomial time learning algorithm for finite unions of term trees by using restricted equivalence, membership, and subset queries. This result indicates the hardness of learning finite unions of term trees in the exact learning model.The exact learning model by Angluin (1988) is a mathematical model of learning via queries in computational learning theory. A term tree is a tree pattern consisting of ordered tree structures and repeated structured variables, which occur more than once. Thus, a term tree is suited for representing common tree structures based on tree-structured data, such as HTML and XML files on the Web. In this paper, we consider the learnability of finite unions of term trees with repeated variables in the exact learning model. We present polynomial time learning algorithms for finite unions of term trees with repeated variables by using superset and restricted equivalence queries. Moreover, we show that there exists no polynomial time learning algorithm for finite unions of term trees by using restricted equivalence, membership, and subset queries. This result indicates the hardness of learning finite unions of term trees in the exact learning model.

Journal

  • 情報処理学会論文誌数理モデル化と応用(TOM)

    情報処理学会論文誌数理モデル化と応用(TOM) 2(3), 127-137, 2009-12-11

Codes

  • NII Article ID (NAID)
    110007989948
  • NII NACSIS-CAT ID (NCID)
    AA11464803
  • Text Lang
    ENG
  • Article Type
    Article
  • ISSN
    1882-7780
  • Data Source
    NII-ELS  IPSJ 
Page Top