数理解析研究所講究録 1325 巻 2003 年 69-74

69
Polynomial Time Inductive Inference of Ordered Term Trees
with Contractible Variables from Positive Data
鈴木祐介 (Yusuke Suzuki), 正代隆義 (Takayoshi Shoudai)
九州大学システム情報科学 {府, 研究院} 情報理学 {専攻, 部門}.

Department of Informatics, Kyushu University{ y-suzuki shoudai}@i. kyushu-u.ac.jp
松本哲志 (Satoshi Matsumoto)東海大学 理学部 情報数理学科

Department of Mathematical Sciences, Tokai University
matumoto@ss. uTokai.ac.jp
内田智之 (Tomoyuki Uchida), 宮原哲浩 (Tetsuhiro Miyahara)
広島市立大学 情報科学部

Faculty of Information Sciences, Hiroshima City University{ uchida@cs, miyahara@its}.hiroshima-cu.ac.jp

1Introduction
Due to the rapid growth of Internet usage, tree structured data such as Web documents have been
rapidly increasing. In order to analyze such tree structured data, efficient learning from tree structured
data becomes more and more important. Tree structured data such as
files are represented
by rooted trees with ordered children and edge labels [1]. In order to represent atree structured patterncommon to such tree structured data, we proposed an ordered term tree, which is arooted tree withordered children and structured variables [7]. Avariable can be substituted by an arbitrary tree. An
ordered term tree is said to be regular if all variable labels in are mutually distinct. Many tree
structured data such as
files have no rigid structure and have essential information in
subtrees containing leaves. In order to deal with such tree structured data, we introduce anew tyPe ofvariable, called acontractible variable, which is regarded as an anonymous subtree in an ordered term
tree and matches any subtree including asingleton vertex. Ausual variable, called an uncontractible
variable, in aterm tree does not match asingleton vertex.
The language of aregular ordered term tree is the set of all ordered trees which are obtained ffom
by substituting ordered trees for variables in . The language of aregular ordered term tree shows therepresenting power of . Aleast generalized regular ordered term tree explaining given tree structured
data is aterm tree whose language contains and is minimal. Consider the examples in Fig. 1. The
term tree is aleast generalized regular ordered term tree for Ti,
and . The ordered term tree
also explains the three trees. But explains any tree with 2or more vertices. So is overgeneralized
and meaningless.
Let be aset of edge labels used in tree structured data.
denotes the set of all regular ordered
term trees all of whose contractible variables are adjacent to leaves. First we give an efficient polynomial
time algorithm for deciding whether or not agiven regular ordered term tree inmatches atree,, we give apolynomial time algorithm for finding aleast generalized
where. Second whenregular ordered term tree inwhich explains all given data. These results imply that the classwithis polynomial time inductively inferable from positive data.
An ordered term tree is different from other representations of ordered tree structured patterns suchas in [2, 4, 13] in that an ordered term tree has structured variables which can be substituted by arbitraryordered trees. We showed that some classes of regular unordered term tree languages are polynomial time
inductively inferable from positive data
. In $[10, 12]$ , we showed that some fundamental classes ofregular ordered term tree languages without’ any contractible variable are polynomial time inductively
inferable from positive data. In [6], we showed that some classes of regular ordered term tree languages
without any contractible variable are exactly learnable in polynomial time using queries. In [7], we gave
adata mining method from semistructured data using ordered term trees.
$\mathrm{H}\mathrm{T}\mathrm{M}\mathrm{L}/\mathrm{X}\mathrm{M}\mathrm{L}$

$t$

$t$

$\mathrm{H}\mathrm{T}\mathrm{M}\mathrm{L}/\mathrm{X}\mathrm{M}\mathrm{L}$

$t$

$t$

$t$

$t$

$t$

$S$

$t$

$S$

$t$

$t_{2}$$T_{2}$$t_{1}$$T_{3}$$t_{1}$$t_{1}$$\Lambda$$\mathcal{O}\Gamma\Gamma_{\Lambda}^{c}$$m_{\Lambda}^{c}$$|\Lambda|\geq 1$$|\Lambda|\geq 2$$\mathcal{O}\Gamma\Gamma_{\Lambda}^{\mathrm{c}}$$O\Gamma\Gamma_{\Lambda}^{\mathrm{c}}$$|\Lambda|\geq 2$$[5, 8_{\lambda}9]$70$\mathrm{n}2\mathrm{O}$$g_{2}$

and . An uncontractible (resp. contractible) variable is represented
Fig. 1. Term trees , and trees ,by asingle (resp. double) lined box with lines to its elements. The label inside abox is the variable label of the$T_{1}$$t_{2}$$t_{1}$$T_{3}$$T_{2}$

variable.

2Ordered Term Trees with Contractible Variablesof vertices
Let $T=(V_{T}, E_{T})$ be arooted tree with ordered children (or simply atree) which has aset
be apartition of Et, i.e.,
. And
and
of edges. Letandand asetis called a $tem$ tree, and elements in ,andare called
let $V_{g}=V_{T}$ . Atriplet $g=$
avertex, an edge and avariable, respectively. We assume that every edge and variable of aterm tree islabeled with some words from specified languages. Alabel of avariable is called avariable label. and$V\tau$$E_{T}$$E_{g}\cap H_{g}=\emptyset$$E_{g}\cup H_{\mathit{9}}=E_{T}$$H_{g}$$E_{g}$$(V_{g},E_{g}, H_{g})$$V_{g}$$E_{g}$$H_{g}$$\Lambda$

denote aset of edge labels and aset of variable labels, respectively, where $\cap X=\phi$ . For aterm, :of distinct vertices of
to is asequence , ,and , apath ffom
tree and its vertices$1\leq
j<i$
,
which
.
any
an
or
avariableconsists of
and
edge
with
there
exists
that
for
9such
If there is an edge or avariable which consists of and such that lies on the path from the root to, then is said to be the parent of and is achild of . We use anotation $[v, v’]$ to represent avariable $\{v, v’\}\in H_{g}$ such that is the parent of . Then we call the parent port of $[v, v’]$ and thechild port of $[v,v’]$ .
$\Lambda$$\mathrm{X}$

$g$

$v:$

$v_{1}$$v_{1}$$v_{1}$$v_{i}$$v_{2}$$\ldots$$v$$j$$v_{j}$

$v’$

$v$

$v’$

$v’$

$v$

$v’$

$v$

$v’$

$v$

$v_{j+1}$

$v$

$v’$

$v$

controctible variable
Definition 1. Let
be adistinguished subset of $X$ . We call variable labels inlabels. Acontractible variable label can be attached to avariable whose child port is aleaf. We callavariable with acontractible variable label acontractible variable, which is allowed to substituteatree with asingleton vertex, as stated later. We call avariable which is not acontractible variable
an uncontractible variable. For avariable $[v,v’]$ , when we pay attention to the kind of the variable, we
and $[v, v’]^{u}$ acontractible variable and an uncontractible variable, respectively.
denote by$X^{c}$$X^{c}$$[v,v’]^{\mathrm{c}}$Aterm tree$u$

is called ordered if every internal vertex in has atotal ordering on all children of. An ordered term tree 9is called regular if an
is denoted byhave mutually distinct variable labels in $X$ . For aset , the number of elements in is
$u$

$g$

. The ordering on the children ofvariables in$H_{g}$

denoted by

$|S|$

$u$

$g$

$<_{u}^{g}$

$S$

$S$

.

Definition 2. An ordered term tree with no variable is called aground ordered term tree, which isdenotes the set of all ground ordered term trees whose edge labels are inastandard ordered tree.
A.
denotes the set of all ordered term trees with contractible or uncontractible variables whoselabelsedge
are in . In this paPer, we treat only regular ordered term trees with contractible variables.
Therefore we call it aterm tree simply$\sigma r_{\Lambda}$$\mathcal{O}\Gamma\Gamma_{A}^{\mathrm{c}}$$\Lambda$

71
Let $f=(V_{f}, E_{f}, Hf)$ and $g=(V_{g},E_{g}, H_{g})$ be term trees. We say thatand are isomorphic,
denoted by $f\equiv g$ , if there is abijection fromtosuch that (i) the root of is mapped to
the root of by , (ii) $\{u, v\}\in E_{f}$ if and only if
and the two edges have the sameedge label, (iii) $[u,v]\in Hf$ if and only if, in particular,
if and only if, and (iv) for any internal vertex in which has more than one child, and for any
two children and $u’$ of , $u’<_{u}^{f}u’$ if and only if.
Let’] be alist of two vertices in where is the root of and $u’$ is aleaf of . The form
$x:=[g, \sigma]$ is called abinding for. If is acontractible variable label in , may be atree with asingleton vertex and thus $\sigma=[u,u]$ . It is the only case that atree with asingleton vertex is allowed
for abinding. Anew term tree $f[x :=[g,\sigma]\}$ is obtained by applying the binding $x:=[g, \sigma]$ to in thefollowing way. Let $e=[v, v’]$ be avariable in with the variable label . Let be one copy of and, $w’$ the vertices of corresponding to , of , respectively. For the variable $e=[v, v’]$ , we attach
to by removing the variable fromand by identifying the vertices $v,v’$ with the vertices , $w’$ of, respectively. If is atree with asingleton vertex, i.e., $u=u’$ , then becomes identical to after thebinding. Asubstitution is afinite collection of bindings $\{x_{1}:=[g_{1},\sigma_{1}], \cdots,x_{n}:=[g_{n}, \sigma_{n}]\}$ , where ’s
are mutually distinct variable labels in $X$ . The term tree , called the instance of by , is obtained
by aPplying the all bindings $x::=[g_{i}, \sigma:]$ on simultaneously. Further we define anew total ordering
on every vertex of in anatural way. In this paPer, we omit the exact definition of the ordering
after applying abinding to aterm tree. The readers can refer it to [10] or [12].
For example, let be aterm tree described in Fig. 1and $\theta=\{x:=[g_{1}, [u_{1},v_{1}]],y:=[g_{2}, [u_{2},u_{2}]]\}$
be asubstitution, where and are trees in Fig. 1. Then the instanceof the term tree by isthe treein Fig. 1.
$f$

$g$

$g$

$f$

$V_{g}$$V_{f}$$\varphi$$\{\varphi(u), \varphi(v)\}\in E_{g}$$\varphi$$[\varphi(u), \varphi(v)]\in H_{g}$$[\varphi(u), \varphi(v)]^{\mathrm{c}}\in H_{\mathit{9}}$

$u’$

$u$

$[u, v]^{\mathrm{c}}\in H_{f}$

$f$

$u$

$\varphi(u’)<_{\varphi(u)}^{g}\varphi(u’)$$\sigma=[\mathrm{u},\mathrm{v}]$

$u$

$g$

$x$

$g$

$g$

$X^{c}$

$x$

$g$

$u$

$f$

$f$

$g’$

$w$

$u$

$f$

$g$

$g’$

$g$

$H_{f}$

$e$

$g’$

$u’$

$g’$

$x$

$w$

$v’$

$v$

$g$

$\theta$$x_{i}$$f$$\mathrm{f}\mathrm{O}$$\theta$$f$$<_{v}^{f\theta}$$v$$f\theta$$t_{2}$$g_{1}$$t_{2}\theta$$g_{2}$$t_{2}$$\theta$$T_{3}$

3An Efficient Matching Algorithm for Term Trees
Amatching algorithm for term trees is an algorithm which decides whether or not aterm tree matches
atree . We gave matching algorithms for term trees with no contractible variable in [10] and forterm trees with variables having more than two child ports in [11]. In this section, we give amatchingalgorithm forby extending the matching algorithm in [10].
, respectively. We
Let $t=(V_{t}, E_{t},H_{t})$ and $T=(V\tau,E_{T})$ be aterm tree inand atree inassume that all vertices of aterm tree are associated with mutually distinct numbers, called vertex
identifiers. We denote by $I(u’)$ the vertex identifier of $u’\in V_{t}$ . Acorrespondence-set ( -set for short)
is aset of vertex identifiers, which are with or without parentheses, of vertices of . Avertex identifier
with parentheses shows that the vertex is achild port of avariable.
Our matching algorithm proceeds by constructing -sets for each vertex of agiven tree in thebottom-up manner, that is, from the leaves to the root of . At first, we construct the C-set-attachingrule of avertex $u’$ of as follows. Let ,, , be all ordered children of $u’$ . The C-set-attaching rule$u’$
$I(u’)\Leftarrow
J(c_{1}’)$of is of the form
, ,) whereis an edge, $J(c_{i}’)=I(\emptyset)$if$[u’,d_{}]$$J(d\dot{.})=(I(c^{}.))$
ifis acontractible variable,
is aspecial symbol which shows isotherwise.
the child port of acontractible variable. The C-set-attaching rule of , denoted by Rule(t), is defined as
$t$

$T$

$\mathcal{O}\Gamma\Gamma_{\Lambda}^{\mathrm{c}}$$U\Gamma_{\Lambda}$$\mathcal{O}\Gamma\Gamma_{A}^{\mathrm{c}}$$t$$\mathrm{C}$

$t$

$T$

$\mathrm{C}$

$T$

$t$

$\cdots$$c_{1}’$$\ldots$$c_{m}’$$J(c’.\cdot)=I(c_{\dot{1}}’)$$\mathrm{J}\{\mathrm{d}\mathrm{m},$$\{u’,d.\cdot\}$$I(\emptyset)$$d_{i}$$t$follows.

Rule(t)$=${{ the C-set-attaching rule of all inner vertices}{ $(I(u’))\Leftarrow(I(u’))|u’$ is the child port of an uncontractible variable}$I(u’)\Leftarrow J(d_{1})$$\cup$,$\ldots$,$\mathrm{J}\{\mathrm{d}$$)|$has just one child and connects tothe child with acontractible variable}.
The algorithm (Fig. 2) runs for $|\Lambda|=1$ . Amatching algorithm forcan be easily constructed
ffom this algorithm. The only work we have to do is to check whether or not edge labels of atree is thesame as corresponding edge labels of aterm tree at the first foreach-loop of -SET-ATTACHING. Then
we can prove this theorem in asimilar way to the proof of the correctness of the matching algorithm
for aterm tree [10].
$\cup\{I(u’)\Leftarrow I(u’)|u’$$|\Lambda|\geq 2$$\mathrm{C}$

Theorem 1. Let be a term tree with vertices inand a tree with $N$ vertices inproblem for deciding whether or not matches is solvable in $O(nN)$ $tree$ .
$t$

$n$

$t$

$m_{A}^{\mathrm{c}}$

$T$

$T$

$\mathcal{O}\Gamma_{A}$

. The

72
Procedure MATCHING(t, );with root $R$ ;with root , :atree in
input :aterm tree in
begin
Construct Rule(tl ;foreach leaf of do$CS(\ell):=\{I(\ell’)|\ell$’is aleaf ofthat is not achild port of acontractible variable,or has just one child and connects to it with acontractible variable};. has no -set and all children of have C-sets
while there is avertex of
do C-Set-Attaching(v, Rule{t) ;
$T$

$t$

$r$

$O\Gamma\Gamma_{\Lambda}^{c}$$T$$\mathcal{O}\Gamma_{\Lambda}$$T$$\ell$$t$$\ell$$T\mathrm{s}.\mathrm{t}$$v$$\mathrm{C}$

$v$

$v$

$)$

if $I(r)$ $\in CS(R)$ then matches
end.
$t$

$T$

else does not match
$t$

$T$

Procedure -SET-ATTACHING( , Rule(t)) ;input :avertex of , Rule(t): the C-set-attaching rule of ;begin
$CS(v):=\emptyset$ ;,be all ordered children of in ;Let ,, $J(c_{m’}’)$ in Rule(t) do,
foreach.
if there is asequencethen $j:-j\dot{.}-1=1$ and $I(c’.\cdot)\in CS(cj:)$ ,1. if
for some : $(j.\cdot-1<k_{:}\leq j)$or
2. if
then $CS(c_{k}.)$ has.
have no condition on when
for all $i=1$ , ,then $CS(v):=CS(v)\cup\{(I(u’)\}j$
foreach $(I(u’))\Leftarrow(I(u’))$ in Rule(t) do, $CS(c_{m})$ which has $I(u’)$ or $(I(u’))$ then $CS(v):=CS(v)\cup\{(I(u’)\}$ ;if there is aset in $CS(c_{1})$ ,foreach $I(u’)\Leftarrow I(u’)$ in Rule(t) do $CS(v):=CS(v)\cup\{I(u’)\}$$v$$\mathrm{C}$

$T$

$v$

$c_{1}$$t$$\cdots$$I(u’)\Leftarrow J(c_{1}’)$

$T$

$v$

$c_{m}$$\cdots$$0=jo\leq j_{1}\leq\cdots\leq j*\cdot\leq\cdots\leq j_{m’-1}\leq j_{m’}=m\mathrm{s}.\mathrm{t}$$J(c_{j}’)=I(c_{\dot{l}}’)$$I(c’.\cdot)$$J(c_{\dot{1}}’)=(I(c’\dot{.}))$.

$k$$(I(c’.\cdot))$$j$$m’//\mathrm{w}\mathrm{e}$$\ldots$$J(c_{\mathrm{i}}’)=I(\emptyset)$$\cdots$

$)$

end.

Fig. 2. An algorithm for deciding whether or not aterm tree$t\in \mathcal{O}\Gamma\Gamma_{\Lambda}$

matches atree$T\in \mathcal{O}\Gamma_{A}$, where$|\Lambda|=1$.

4Algorithms for Finding aLeast Generalized Term TreeIn this section, we present polynomial time algorithm for finding aleast generalized term tree where
to be the descriptive, explaining given semistructured data. We can consider the language
is aterm
power of aterm tree . Aleast generalized term tree explaining agiven set of trees. The problem
and there is no term tree satisfying thattree such that(;for finding aleast generalized term tree for agiven set of trees is discussed as the minimal language
problem (MINL for short) in computational learning theory. The main algorithm is described in Fig. 4.
$L_{\Lambda}(t)$$|\Lambda|\geq 2$$S\subseteq \mathcal{O}\Gamma_{\Lambda}$

$t$

$t’$

$S\subseteq L_{\Lambda}(t)$$t$Lemma 1. Let
Fig. 3. Then

$g$

and

$t$

be $tem$ trees in$L_{\Lambda}(g)=L_{\Lambda}(t)$Fig. 3. Cases 1-3:
corresponding parts$g\not\equiv t$$A$$\mathcal{O}\Gamma\Gamma_{A}^{\mathrm{c}}$for anyfor$|\Lambda|\geq 2$.

and$L_{\Lambda}(g)=L_{\Lambda}(t)$, $B$ , $C$, $D$ of .
$t$

$S\subseteq L_{\Lambda}(t’)$$\Lambda$$L_{\Lambda}(t)$which are described in one of Cases 1-3 of. The parts$A$, $B$ , $C$, $D$ of$g$

are the same as the73
Algorithm MINL(S);input: aset of trees;
output :aleast generalized term tree for ;
begin
Let
be the set of all edge labels which appear in ;$t:=(\{u, v\}, \emptyset, \{[u, v]\})$ ;Letbe alist initialized to be $[[u, v]]$ ;;VARIABLE-EXTENSION
Let be the root of ;EDGE-REPLACING $(t, S, r_{t})$ ;outputend.
Procedure VARlABLE-ExTENsloN $(t:nput, S, q)$ ;input input : aterm tree, :aset of trees, :aqueue of variables;
begin$S=\{T_{1}, \ldots, T_{m}\}\subseteq U\Gamma_{\Lambda}$

$S$

$t$

$S$

$\Lambda s$$q$$(\mathrm{t}, S, q)$$t$$r_{t}$

$t$

$S$

$q$

.
$t:=t_{*nput;}$

is not empty do begin, , and W3 be new vertices;$//w_{1}$ becomes avertex between
and .
$t’:=$ (Vi$v]\}-\{[u,$ $v]\}$ ), Et, $H_{t}\cup\{[u,$ifthen begin $t:=t’$ ; $q:=q\ [[w_{1},v]]$ ;continue end else $q:=q[2..]$ ;$//w_{2}$ and W3 become the previous and next siblings of, respectively.
$t’:=$;] end;
ifthen begin $t:=t’;q$ :=q&[[u,

while

$q$

$[u, v]:=q[1]$ ;Let$w_{1}$$w_{2}$$u$$\cup\{w_{1}\}$$v$$w_{1}],$ $[w_{1},$$\mathrm{i}$$S\subseteq L_{\Lambda}(t’)$$v$$(\mathrm{V}\mathrm{C}\cup\{w_{2}\}, E_{t}, H_{t}\cup\{[u, w_{2}]\})$$S\subseteq L_{\Lambda}(t’)$$w_{2}]$$t’:=(V_{t}\cup\{w_{3}\}, E_{t}, H_{t}\cup\{[u, w_{\theta}]\})$

if$S\subseteq L_{A}(t’)$

end;returnend;;

then begin $t:=t’j$ q:=q&[[u,$w\mathrm{a}]$] end;$t$

Procedure EDGE-REpLACING(t.nPut, $S,u$ );input input : aterm tree, :aset of trees, :avertex;
begin
if is aleaf then return;,be the children of ;$t:=t:nput$ ;Letfor : $:=1$ to do LABELED-EDGE-REPLACING $(4S, v_{i})$ ;for : $:=1$ to do
foreach edge label A $\in As$ do, , andbe an edge with label Aandnew vertices;previous and next siblings of , respectively, and if :is aleaf,
if :is aleaf then begin
$S$

$u$

$u$

$v_{1}$$\ldots$

$Vk$

$u$

$k$

$k$

$//\mathrm{L}\mathrm{e}\mathrm{t}\{u, v.\}$$w_{2}$$w_{1}$$w\mathrm{s}$

$v$

$v:$

$//\mathrm{t}\mathrm{h}\mathrm{e}$andbecomebecomes achild of$w_{1}$$w\theta$$w_{2}$$v$;$t’:=(V_{t}\cup\{w_{1}, w_{2}, w_{3}\}, E_{t}\cup\{\{u, v.\cdot\}\}, H_{t}\cup\{[u, w_{1}]^{\mathrm{c}}, [u, w_{2}]^{\mathrm{c}}, [v., w_{3}]^{\mathrm{c}}\}-\{[u, v:]\})$

if $S\subseteq L_{A}(t’)$ then begin;if$S\subseteq L_{A}(t_{1})$);if$S\subseteq L_{\Lambda}(t_{2})$$t_{1}:=(\mathrm{V}\mathrm{t}-\{w_{1}\}, E_{t’}, H_{t’}-\{[u,w_{1}]^{\mathrm{c}}\})$$t_{2}:=$(Vt$-\{w_{2}\},$ $E_{t’},$ $H_{t’}-\{[u,w_{2}]^{\mathrm{c}}\}$$t_{3}:=$ $(V_{t’}-\{w_{3}\}, E_{t’}, H_{t’}-\{[v:, w_{S}]^{e}\})$$t$$:=t’$ ;;if$S\subseteq L_{A}(t_{3})$then $t’:=t_{1j}$then $t’:=t_{2}$ ;then $t’:=t_{3}$ ;continueend
end else begin;$t’=(V_{t}\cup\{w_{1},w_{2}\}, E_{t}\cup\{\{u, v:1\}, H_{t}\cup\{[u, w_{1}]^{e}, [u, w_{2}]^{c}\}-\{[u,v:]\})$

if$S\subseteq L_{\Lambda}(t’)$$t_{1}:=$(Vt

then begin$-\{w_{1}\},E_{t’},$ $H_{\ell’}-\{[u,$$w_{1}]^{\mathrm{c}}\}$

);if
;if

$t_{2}:=(\mathrm{V}\mathrm{t}-\{w_{2}\}, [\mathrm{t}\mathrm{i}, H_{l’}-\{[u,w_{2}]^{\epsilon}\})$

$t$

$:=t$

end
end;
return’: continue$S\subseteq L_{4}(t_{1})$$S\subseteq L_{\Lambda}(t_{2})$then $t’:=t_{1}$ ;then $t’:=t_{2}$ ;

$t$

end;

Fig. 4. Algorithm MINL

$v_{\tau}$

74
for $|\Lambda|>2$ . The term tree is said to be acanonical $tem$
Definition 3. Let be aterm tree inedgesof the right term trees described in Cases 1-3. For
andvariablesoftree if has no combinationbythecanonical term tree such that
intotransform
an arbitrary term tree , we canlefttrees.
transforming the right trees in Cases 1-3 into the
$t$

$t$

$\mathcal{O}\mathit{7}\Gamma_{\Lambda}^{c}$

$t$

$t$

$t$

$t$

Lemma 2. Let and be canonical term trees in.
a substitution such that
$t$

$g$

$L_{\Lambda}(g)=L_{\Lambda}(t)$$g$$\mathcal{O}\Gamma\Gamma_{\Lambda}^{\mathrm{c}}$for any . If$\Lambda$$L_{\Lambda}(g)\subseteq L_{\Lambda}(t)$then there exists$g\equiv t\theta$$\theta$

The procedure VARIABLE-EXTENSION extends aterm tree by adding uncontractible variables asmuch as possible. Aterm tree outputted by VARIABLE-EXTENSION is aleast generalized term tree forconsisting of only uncontractible variables. Then the procedure EDGE-REpLAClNG tries to replace
variables with labeled edges from leaves to the root. Since the output term tree is not larger than thelargest tree in , we have the following lemma.
$S$

$S$

be the output of the algorithm MINL for an input S. Let be a term tree satisfying
andbe the canonical $tem$ trees such that
. Let and
$L_{\Lambda}(g’)=L_{J1}(t’)$ , respectively. Then.

Lemma 3. Let
that
$S$

$t’$

$t$

$\subseteq L_{\Lambda}(t’)\subseteq L_{\Lambda}(t)$$g$$L_{\Lambda}(g)=L_{\Lambda}(t)$$g’$$g\equiv g’$

Theorem 2. Let
term tree inbe a set of edge labels where
for a given set of trees in$\Lambda$$\mathcal{O}\Gamma\Gamma_{\Lambda}^{\mathrm{c}}$. The algorithm MINL finds a least generalizedin polynomial time.

$|\Lambda|\geq 2$$U\Gamma_{A}$In this paper, we have presented polynomial time algorithms for solving the membership and MINL
problems for the class of labeled term trees. From these algorithms and Angluin’s theorem [3], we canshow that the class is polynomial time inductively inferable ffom positive data.

References
1. S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: nvm Relations to Semistructured Data andXML. Morgan Kaufmann, 2000.
2. T. R. Amoth, P. Cull, and P. Tadepalli. Exact learning of unordered tree patterns from queries. Proc.
COLT-99, A CM Press, pages 323-332, 1999.
3. D. Angluin. Finding patterns common to aset of strings. Journal of Computer and System Science, 21:46-62,

1980.
4. H. Arimura, H. Sakamoto, and S. Arikawa. Efficient learning of semi-structured data from queries. Proc.
$ALT$-2001, Springer- Verlag, LNAI 2225, pages 315-331, 2001.
5. S. Matsumoto, Y. Hayashi, and T. Shoudai. Polynomial time inductive inference of regular term tree
languages from positive data. Proc. ALT-97, Springer, Verlag, LNAI 1316, pages 212-227, 1997.
6. S. Matsumoto, T. Shoudai, T. Miyahara, and T. Uchida. Learning of finite unions of tree patterns withinternal structured variables from queries. Proc. $AI$-2002, Springer- Verlag, LNAI 2557 pages 523-534, 2002.
7. T. Miyahara, Y. Suzuki, T. Shoudai, T. Uchida, K. Takahashi, and H. Ueda. Discovery of frequent tag
tree patterns in semistructured web documents. Proc. PAKDD-20(E, Springer-Verlag, LNAI 2336, pages
341-355, 2002.

8. T. Shoudai, T. Miyahara, T. Uchida, and S. Matsumoto. Inductive inference of regular term tree languages
and its application to knowledge discovery. Info rmation Modelling and Knowledge Bases XI, IOS Press,
pages 85-102, 2000.
9. T. Shoudai, T. Uchida, and T. Miyahara. Polynomial time algorithms for finding unordered tree patterns
with internal variables. Proc. $FCT$-flOOl, Springer- Verlag, LNCS 2138, pages 335-346, 2001.
10. Y. Suzuki, R. Akanuma, T. Shoudai, T. Miyahara, and T. Uchida. Polynomial time inductive inference ofordered tree patterns with internal structured variables from positive data. Proc. COLT-2002, SpringerVerlag, LNAI 2375, pages 169-184, 2002.
11. Y. Suzuki, T. Shoudai, T. Miyahara, and T. Uchida. Apolynomial time matching algorithm of structuredordered tree patterns for data mining from semistructured data. Proc. $ILP$-flOOfl, Springer-Verlag, LNAI
2583, pages 270-284, 2003.
12. Y. Suzuki, T. Shoudai, T. Uchida, and T. Miyahara. Ordered term tree languages which are polynomial
time inductively inferable from positive data. Proc. $ALT$-2002, Springer- Verlag, LNAI 2533, pages 188-202,

2002.
13. K. Wang and H. Liu. Discovering structural association of semistructured data. IEEE Trans. Knowledge
and Data Engineering, $12:35\succ 371$ ,2000.