2007 | OriginalPaper | Chapter
Exact Learning of Finite Unions of Graph Patterns from Queries
Authors : Rika Okada, Satoshi Matsumoto, Tomoyuki Uchida, Yusuke Suzuki, Takayoshi Shoudai
Published in: Algorithmic Learning Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
A linear graph pattern is a labeled graph such that its vertices have constant labels and its edges have either constant or mutually distinct variable labels. An edge having a variable label is called a variable and can be replaced with an arbitrary labeled graph. Let
${\mathcal GPC}$
be the set of all linear graph patterns having a structural feature
${\mathcal C}$
like “having a tree structure”, “having a two-terminal series parallel graph structure” and so on. The graph language
GLc
(
g
) of a linear graph pattern
g
in
${\cal GP}({\mathcal C})$
is the set of all labeled graphs obtained from
g
by substituting arbitrary labeled graphs having the structural feature
${\mathcal C}$
to all variables in
g
. In this paper, for any set
${\cal T_*}$
of
m
linear graph patterns in
${\cal GP}({\mathcal C})$
, we present a query learning algorithm for finding a set
S
of linear graph patterns in
${\cal GP}({\mathcal C})$
with
$\bigcup_{g\in{\cal T_*}}GLc{(g)}=\bigcup_{f\in S}GLc{(f)}$
in polynomial time using at most
m
+ 1 equivalence queries and
O
(
m
(
n
+
n
2
)) restricted subset queries, where
n
is the maximum number of edges of counterexamples, if the number of labels of edges is infinite. Next we show that finite sets of graph languages generated by linear graph patterns having tree structures or two-terminal series parallel graph structures are not learnable in polynomial time using restricted equivalence, membership and subset queries.