2007 | OriginalPaper | Buchkapitel
Exact Learning of Finite Unions of Graph Patterns from Queries
verfasst von : Rika Okada, Satoshi Matsumoto, Tomoyuki Uchida, Yusuke Suzuki, Takayoshi Shoudai
Erschienen in: Algorithmic Learning Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.