We consider learning tree patterns from queries extending our preceding work [Amoth, Cull, & Tadepalli, 1998] . The instances in this paper are unordered trees with nodes labeled by constant identifiers. The concepts are tree patterns and unions of tree patterns (unordered forests) with leaves labeled with constants or variables. A tree pattern matches any tree with its variables replaced with constant subtrees. A negative result for learning with equivalence and membership/subset queries is shown for unordered trees where a successful match requires the number of children in the pattern and instance to be the same. Unordered trees and forests are shown to be learnable with an alternative matching semantics that allows an instance to have extra children at each node. 1 INTRODUCTION Many applications in mathematics and language processing represent data more naturally as trees (or as unions of these) than as vectors of features. Tree patterns also provide more information than simple s...

We consider learning tree patterns from queries. The instances are ordered and unordered trees with nodes labeled by constant identifiers. The concepts are tree patterns and unions of tree patterns (forests) where all the internal nodes are labeled with constants and the leaves are labeled with constants or variables. A tree pattern matches any tree with its variables replaced with constant subtrees. We show that ordered trees, in which the children are matched in a strict left-to-right order, are exactly learnable from equivalence queries, while ordered forests are learnable from equivalence and membership queries. Unordered trees are exactly learnable from superset queries, and unordered forests are learnable from superset and equivalence queries. Negatively, we also show that each of the query types used is necessary for learning each concept class. 1 INTRODUCTION A large part of computational learning theory is devoted to learning concepts over instances represented as attribute v...