### Finding tree patterns consistent with positive and negative examples using queries

**Authors: Hiroki Ishizaka, Hiroki Arimura and Takeshi Shinohara**.

Email: arim@.i.kyushu-u.ac.jp

**Source: ***Annals of Mathematics and Artificial Intelligence*
Vol. 23, No. 1-2, 1998, 101-115.

**Abstract.**
This paper is concerned with the problem of finding a hypothesis in TP^{2} consistent with given
positive and negative examples. The hypothesis class TP^{2} consists of all sets of at most two tree
patterns and represents the class of unions of at most two tree pattern languages. Especially, we
consider the problem from the point of view of the consistency problem for TP^{2}. The consistency
problem is a problem for deciding whether there exists a consistent hypothesis with given positive
and negative examples within some fixed hypothesis space. Efficient solvability of that problem is
closely related to the possibility of efficient machine learning or machine discovery.
Unfortunately, however, the consistency problem is known to be NP-complete for many
hypothesis spaces. In this paper, the problem for the class TP^{2} is also shown to be NP-complete. In
order to overcome this computational hardness, we try to use additional information obtained by
making queries. First, we give an algorithm that, using restricted subset queries, solves the
consistency problem for TP^{2} in time polynomial in the total size of given positive and negative
examples. Next, we show that each subset query made by the algorithm can be replaced by several
membership queries under some condition on a set of function symbols. As a result, we have that
the consistency problem for TP^{2} is solved in polynomial time using membership queries.

©Copyright 1998 Baltzer Science Publishers