Abstract:
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.
