数理解析研究所講究録1093 巻 1999 年 117-122

117

Refutable Inference of Formal Graph Systenls
and NLC Graph Grammars
Tetsuhiro Miyahara (宮原哲浩)\dagger

Tomoyuki Uchida (内田智之)\dagger

Takayoshi Shoudai (正代隆義)\downarrow

Kenichi Takahashi (高橋健–)\dagger

Hiroaki Ueda (上田祐彰)\dagger\dagger Faculty of Information Sciences, Hiroshima City University

Hiroshima 731-3194, Japan{miyahara@its, uchida@cs, takahasi@its, ueda@its}. hiroshima-cu.
\ddagger Department of Informatics, Kyushu University 39
Kasuga 816-8580, Japan
shoudai@i. kyushu-u.

Abstract
A graph is one of the most common abstract structures and is suitable for representing relations between various objects.
The analyzing system directly manipulating graphs is useful for knowledge discovery. Formal Graph System (FGS) is akind of logic programming system which
directly deals with graphs just like first order terms. We have designed and implemented a knowledge discovery system KDFGS, which receives the graph data andproduces a hypothesis by using FGS as aknowledge representation language. The
system consists of an FGS interpreter anda refutably inductive inference algorithm
for FGSs.
In this paper, we show that sufficiently
large hypothesis spaces of FGS programs
are refutably inferable and thus give a theoretical foundation of KD-FGS. We report
some experiments of running KD-FGS andsystem is useful for knowlconfirm
edge discovery from graph data. We also
consider refutable inference of NLC graphgrammars.
$\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}‘ \mathrm{t}\mathrm{h}\mathrm{e}$1. Introduction
Machine learning and data mining technology have been used for knowledge discovery and prediction in many fields [4].
The aim of knowledge discovery is to finda small and understandable hypothesis$\mathrm{a}\mathrm{c}$. jp$\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}$which explains data nicely. A graph is oneof the most common abstract structuresand is suitable for representing relations
between various objects [10]. We believethat the analyzing system directly dealing
with graphs is useful for knowledge discovery.
Formal Graph System (FGS, [8]) is akind of logic programming .ystem which
directly deals with graphs just like firstorder terms. So FGS is suitable to represent logical knowledge explaining given
graph data. We have designed and implemented a knowledge discovery
KDFGS (
Figure 1), which recelves graphdata and produces a hypothesis by using
FGS as a knowledge representation language. As inputs, the system receives positive and negative examples of graph data.
As an output, the system produces an FGS
program which is consistent with the positive and negative examples if such a hypothesis exists. Otherwise, the system re$\mathrm{s}$.stem$\mathrm{s}\mathrm{y}$$\mathrm{s}e\mathrm{e}$futes the hypothesis space. KD-FGS consists of an FGS interpreter and a refutably
inductive inference algorithm of FGS programs. The FGS interpreter is used tocheck whether a hypothesis is consistent
with the given graph data or not.
A refutably inductive inference algorithm, proposed by Mukouchi and Arikawa[5], is a special type of inductive inference
algorithm with refutability of hypothesis
spaces. Suppose that a hypothesis spaceis refutably inferable and data are succes-

118

Figure 1: KD-FGS: a knowledge discovery system from graph data using FGS
sively iven to the algorithm for the hypothesls space. If there exists a hypothesis describing the data in the hypothesis
space, hen the algorithm will infer the hypothesls, that is, .it will eventually iden. If not, then the altify thegorithm will refute the hypothesis space.’that is, it will tell us that noin the hypothesis space explains the dataand stop. When the hypothesis space isrefuted, KD-FGS chooses another hypothesis space and tries to make a discovery
in the new . pothesis space. By refut.ing
space, the algorithm
theimportant suggestions to achieve the goalof knowledge discovery. Thus, KD-FGS isuseful for knowledge discovery from graphdata. KD-FGS is based on FGS, which isa kind of graph generating systems. We
show that the method of KD-FGS is also
based
to the discovery syst
on NLC graph grammar, which is a famousgraph generating system.
This paper is organized as follows.
In Section 2, we introduce FGS as a
new knowledge representation language forgraph data. In Section 3, we give ourframework of refutably inductive inferenceof FGS programs. For constant $n\geq 0$ , weshow that the hypothesis spaces of weakly
reducing or size-bounded FGS programswith at most graph rewritin.g rules area theorefutably inferable. Thus weretical foundation of KD-FGS. In Section$.\mathrm{g}$$.\mathrm{t}$4, we report im.plementation of KD-FGS
and some $\exp$ erlmental results: In Section
5, we also consider refutable lnference of
NLC graph grammars.

$\mathrm{h}\mathrm{y}\mathrm{p}_{\mathrm{o}\mathrm{t}}\mathrm{h}e\mathrm{S}\mathrm{l}\mathrm{s}$$\mathrm{h}\mathrm{y}\mathrm{p}_{\mathrm{o}\mathrm{t}\mathrm{h}}\mathrm{e}\mathrm{S}\mathrm{l}\mathrm{s}$$\mathrm{h}\mathrm{y}$$\mathrm{h}\mathrm{y}\mathrm{p}_{\mathrm{o}\mathrm{t}\mathrm{h}}\mathrm{e}\mathrm{s}\mathrm{l}\mathrm{S}$$\mathrm{g}_{1}\mathrm{v}\mathrm{e}\mathrm{s}$$\mathrm{a}\mathrm{p}\mathrm{p}\mathrm{l}\mathrm{i}_{\mathrm{C}}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\omega$$e\mathrm{m}$$n$$\mathrm{g}_{1}\mathrm{v}\mathrm{e}$2. FGS as a New Knowledge
Representation Language
Formal Graph System (FGS, [8]) is a kindof logic programming system which directly deals with graphs just like first orderterms.
Let and A be finite alphabets, and let$X$ be an alphabet, whose element is calleda variable label. Assume that
. A term graph $g=$ (V, $E,$ $H$ ) consistsof a vertex set , an edge set $E$ and amulti-set $H$ whose element is a list of distinct vertices in and is called a variable.
And a term graph has a vert labeling:, an edge labeling:: $Harrow X$ . A
and a variable labeling. For
term graph is called ground if
example, a term graph $g=(V, E, H)$ isshown in Figure 2, where $V=\{u_{1}, u_{2}\}$ ,$\Sigma$$(\Sigma\cup\Lambda)\cap x=$$\emptyset$

$V$

$V$

$e\mathrm{x}$$g$$Varrow\Sigma$$\psi_{g}$$Earrow\Lambda$$\varphi_{g}$$\lambda_{g}$$H=\emptyset$$E=\emptyset,$$H=\{e_{1}=(u_{1}, u_{2}), e_{2}=(u_{1}, u_{2})\}$$\varphi_{g}(u_{1})=s,$$\lambda_{g}(e_{2})=y$$\varphi_{g}(u_{2})=t,$$\lambda_{\mathit{9}}(e_{1})=x$

,

, and

. An atom is an expression of, where is a predithe form
are
and
arity
cate symbol with
$A,$
be
atoms
term graphs. Letwith $m\geq 0$ . Then, a graph rewriting rule$p(g_{1}, \ldots,g_{n})$

$p$

$n$

$g_{1},$$B_{1},$$B_{m}$$\ldots,$$\ldots,g_{n}$119is a clause of the form $Aarrow B_{1},$.
An $FGS$ program is finite set of graphrewriting rules: For example, the FGS programingenerates the familyof all two-terminal series parallel (TTSP)
graphs.
Let be a term .graph and be a listof distinct vertices $\ln g$ . We call the form
$x:=[g, \sigma]$ a binding for a variable label$x\in X$ . A substitution
is a finite collection of bindings$:=$, whereare mutually distinct
variable labels in $X$ and each $g_{i}(1\leq$
has no variable labeled with anelement in. For a set or alist , the number of elements in is denoted by. In the same way as logic
programrmng system, we obtain a newterm graph by applying a substitution
to aterm graph $g=(V, E, H)$ in the following
way. For each binding$(1\leq\dot{i}\leq n)$ in parallel, we
attach toby removing the all variables
labeled withfrom $H$ , and by identifying
the m-th element of and the m-th element offor each $1\leq j\leq k$ and each$1<m\leq|t_{j}|=|\sigma_{i}|$ , respectively. The reterm graph is denoted by . In
Figure 2, for example, we draw the term
graphwhich is obtained by applying asubstitution $\theta=\{x:=[g_{1}, (v_{1},v_{2})],$ $:=$$[g_{2}, (w_{1}, w2)]\}$ to the term graph
A unia subfier of two term graphs andstitution such thatandare isomorphic. In general, there exists no mgu(most general unifier) of two
graphs.
Therefore, in FGS a derivation is based onan enumeration of unifiers and only groundgoal is considered in this paper. A graphrewriting rule is provable from an FGS
programif
is obtained frombyfinitely many applications of graph rewriting rules and modus ponens.
$\ldots,$$B_{m}$$\mathrm{a}_{i}$$\Gamma_{SP}$$\mathrm{F}_{1}\mathrm{g}\mathrm{u}\mathrm{r}\mathrm{e}1$$g$$\sigma$$\theta$$\{x_{1}:=[g_{1}, \sigma_{1}],$$[g_{n}, \sigma_{n}]\}$$\ldots,$$x_{n}$$x_{i}’ \mathrm{s}$$\dot{i}\leq n)$$\{x_{1}, \ldots, x_{n}\}$

$S$

$S$

$|S|$

$f$

$\theta=\{x_{1}:=[g_{1}, \sigma_{1}], \cdots, x_{n} :=[g_{n}, \sigma_{n}]\}$$x_{i}:=[g_{i}, \sigma_{i}]\in\theta$$g$$g_{i}$$t_{1},$$\cdots,$$t_{k}$$x_{i}$$t_{j}$$\sigma_{i}$$f$$\mathrm{s}\mathrm{u}\overline{\mathrm{l}\mathrm{t}}\mathrm{i}\mathrm{n}\mathrm{g}$$g\theta$$g\theta$$y$$g.\cdot$$g_{1}$$\theta$$g_{1}\theta$$g_{21}\mathrm{s}$$g_{2}\theta$$\mathrm{t}e\mathrm{r}\mathrm{m}$$C$$\Gamma$$C$$\Gamma$theory of machine discovery from facts andshowed that refutable inductive inferenceis essential in machine discovery from facts
and the sufficiently large hypothesis spacesof EFSs are refutably inferable.
Let $g=$ (V, $E,$ $H$ ) be agraph.
Then we denote the size of by
and$\mathrm{t}e\mathrm{r}\mathrm{m}$’$\mathrm{d}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}|g|=\mathrm{e}|_{V|+||^{+}|}^{g1=}|V||E|+|H|.\mathrm{F}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{x}E+H|=2+0+2=\mathrm{p}\mathrm{a}\mathrm{m}\mathrm{l}\mathrm{e}4$

for the term graph $g=(V, E, H)$ in
ure 2. For an atom
, we define$||p(g_{1}, \ldots,gn)||=|g_{1}|+\cdots+|g_{n}|$ . An erasing binding is a binding$:.=[g, \sigma]$ suchthat consists of all rtices, no edge
and no variable. An erasing substitution
is a substitution which contains an erasing binding. In this paper, we disallow an
erasing substitution. Thenfor
any term graph and any substitution .
Definition 1. (1) A graph rewriting rule
$Aarrow B_{1},$is said to be weakly reducing if
for any $i=1,$
and any substitution . An FGS programis weakly reducing if every graph rewriting rule in is weakly reducing.
(2) A graph rewriting ruleis said to be-bounded if
for any substitution . An FGS program isbounded if every graph rewriting rule inis size-bounded.
$\cdot$$\mathrm{F}_{1}’\mathrm{g}-$$p(g_{1}, \ldots,g_{n})$

$x$

$g$

In this section, we show that sufficiently
large hypothesis spaces of FGS programs
are refutably inductive inferable and we
present refutably inductive inference algorithms for the hypothesis spaces.
We give our framework of refutably inductive inference of FGS programs according to [1, 5, 7, 9]. Mukouchi and Arikawa[5] originated a computational learning$\ln\sigma$$\mathrm{v}e$$||g\theta||\geq||g||$$\theta$$g$$\ldots,$$B_{m}$$||A\theta||\geq||B_{i}\theta||$$\ldots,$$m$$\theta$$\Gamma$$\Gamma$$A$$B_{1},$$\ldots,$$B_{m}$$arrow$$S\dot{i}ze$$||A\theta||\geq||B_{1}\theta||+\cdots+||B_{m}\theta||$$\theta$$\Gamma$$S\dot{i}Ze-$$\Gamma$A size-bounded FGS program is also
we akly reducin.g. For example, the FGS
programFigure 1 is we akly reducing but not size-bounded. Let $g=$
(V, $E,$ $H$ ) be a term graph. For a variable
label $x\in X$ , the number of variables in $H$labeled with is denoted by $o(x,g)$ . For
example, $o(x,g)=1$ and $o(y,g)=1$ for
the term graph $g=(V, E, H)$ in Figure 2.
For an atom $p(g_{1}, \ldots,g_{n})$ and a variable label $x\in X$ , we define $o(x,p(g1, \ldots,g_{n}))=$$\Gamma_{SP}\ln$$x$$o(x,g_{1})+\cdots+o(X,g_{n})$3. Refutably Inductive Inference of FGS Programs

$|g|$

$g$

.

A hypothesis space also called a class.
We consider the two properties of hypothesis spaces for machine discovery fromfacts. (Property 1) All hypotheses in a hyfor machine discovery must
be recurslvely enumerable. The following
Lemma 1 shows that our target hypothesis spaces have the Property 1. (Property 2) Whether a hypothesis is consistent
with examples or not must be recursively
decidable. The following Lemma 2 showsthat our target hypothesis spaces have theProperty 2.
$1\mathrm{S}$$\mathrm{p}_{\mathrm{o}\mathrm{t}\mathrm{h}1\mathrm{S}\mathrm{s}}\mathrm{e}\mathrm{s}.\mathrm{P}\mathrm{a}\mathrm{C}\mathrm{e}$

120

$g$

$y_{2}$$y_{1}$

Figure 2: Term graphs$[g_{1}, (v_{1}, v2)],$

and

$g$

$g\theta$$y:=[g2, (w1, w2)]\}$ to$g$.

obtained by applying a substitution $\theta=\{x$ $:=$

Lemma 1. (1) A graph rewriting. rule
$Aarrow B_{1},$is weakly reduclng if
and only if
and $o(x,A)\geq$.
, and any vari$\ldots,$$B_{m}$$||A||$$\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}o(X,$$\geq||B_{i}||$$B1^{i}\mathrm{a}\mathrm{t}_{\mathrm{e}}\mathrm{f}1x\mathrm{o}\mathrm{r}.\mathrm{a}\mathrm{n}\mathrm{y}\iota=1,$

(2) A
,

$\ldots$$m$

gr.aph. rewriting rule$A$$arrow$

slze-bounded if and only if$||A||\geq||B_{1}||+\cdots+||B_{m}||$ and $o(x,A)\geq$$o(x, B_{1})+\cdots+o(x, B_{m})$ for any variable
label .
$B_{1},$$B_{m}1\mathrm{S}$$\ldots$

said to converge to an FGS program for apresentation , if there is a positive integer
such that for any $m>m_{0},$ $A(\delta[m])$ isdefined and equal to
be a classof FGS programs. For an FGS program$\Gamma\in FC$ and a predicate-restricted com,
w.r.t.
plete presentation of
an RIIA $A$ is said to be infer the FGS program w.r.t. $FC$ in the limit from , if$\Gamma$$\delta$$m_{0}$$\Gamma.\overline{\mathrm{L}\mathrm{e}}\mathrm{t}FC$$\delta$$M_{\Gamma}$$\Pi_{\mathrm{O}}\underline{\subseteq}\Pi$$\delta$$\Gamma$$x$

For an FGS program
least Herbrand model of F.
$\Gamma,$$M_{\Gamma}$

denotes the

be a weakly reducing
Lemma 2. Letor size-bounded FGS program. Then theof is a recurleast Herbrand model
sively decidable set.
$\Gamma$$M_{\Gamma}$$\Gamma$$\mathrm{W}\mathrm{i}\mathrm{t}^{\mathrm{C}}\mathrm{h}MA\mathrm{o}\mathrm{n}\mathrm{v}_{\Gamma}\mathrm{e}\mathrm{r}_{\ovalbox{\tt\small REJECT}_{\Pi}=M|\mathrm{f}\mathrm{o}\mathrm{r}},\mathrm{e}\mathrm{S}\mathrm{t}\mathrm{o}\mathrm{a}\mathrm{n}\mathrm{F}\mathrm{G}\mathrm{S}\mathrm{p}\mathrm{r}_{\delta}\mathrm{o}\mathrm{o}\Gamma\Pi_{0}.\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\Gamma’\in \mathcal{F}c$

is said to
Definition 2 ([5]). A classbe theoretical-term-freely and refutably in$\mathcal{F}C$

ferable from complete data, if for anyof , there isnonempty finite subset
an RIIA $A$ which satisfies the following
condition: For any set $I\subseteq HB$ and any
predicate-restricted complete presentationof w.r.t.
if there is an FGS pro$\Gamma\in
FC$
,
such
gram
that
in the limit
then $A$ infers
w.r.t.
fromotherwise $A$ refutes the classfrom .
$I$$\delta$

be a finite set of predicate symLetbols. We explain the refutably inductive
inference of FGS programs. The set of
all ground atoms is called the Herbrandbase and denoted by. For an atom ,pred $(A)$ denotes the predicate symbol of. For a set
II and a setofatoms,
denotes the set of atoms in. Thatwhose predicate symbols are in.
is
A predicate-restricted complete presentation of a set $I\subseteq HB$ w.r.t.
is an infinite sequenceof elements in $HB|\Pi_{0}\cross\{+$ ,such that$\{\mathrm{A}|t_{i}=+, i\geq 1\}=I|\Pi_{0}$ and$\{A_{i}|t_{i}= -, \dot{i}\geq 1\}=HB|_{\Pi_{0}}\backslash I|\Pi_{0}$ .
A refutably inductive inference algorithm(RIIA, for short) is a special typ of algorithm that receives a predicate-restrictedcomplete presentation as an input. An
RIIA $A$. is said to refute a class, if $A$ produces the sign“refute”as an output andstops. An RIIA either produces infinitely
many FGS programs as outputs or refutes
a class. For an RIIA $A$ and a presentation$\Pi$$\Pi_{0},$$(\mathrm{i})$$M_{\Gamma}|_{\Pi_{\mathrm{Q}}}=I|_{\Pi_{0}}$$\Gamma$$\delta,$$\mathcal{F}C$$\mathcal{F}^{\cdot}C$$(\mathrm{i}\mathrm{i})$$\delta$$A$$\mathrm{H}\mathrm{B}$

$A$

$\Pi$

$\mathrm{I}\mathrm{I}_{0}$$S$$\mathrm{I}\mathrm{I}_{0}\subseteq$$S$$S|\Pi_{0}$$\mathrm{I}\mathrm{I}_{0}$$S|_{\Pi_{0}}=\{A\in S|pred(A)\in \mathrm{I}\mathrm{I}_{0}\}$$\Pi_{0}\subset\Pi$$(A_{1}, t_{1}),$-$(A_{2},t_{2}\overline{),}\ldots$

$\}$

$e$

$\delta,A\mathrm{d}\mathrm{u}\mathrm{C}\mathrm{e}t_{\mathrm{b}\mathrm{y}\mathrm{e}\mathrm{s}}^{\delta[}m])\mathrm{d}\mathrm{e}\mathrm{n}\mathrm{o}\mathrm{t}\mathrm{e}_{\mathrm{S}}\mathrm{S}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{l}\mathrm{a}\mathrm{s}A\mathrm{W}\mathrm{h}\mathrm{i}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{S}\mathrm{u}\mathrm{c}\mathrm{C}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{l}\mathrm{y}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{S}\mathrm{t}\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{o}\mathrm{d}e-$the first $m$ elements in 6. An RIIA $A$ is

Theoretical terms are supllementary
predicates that are necessary for definingsome goal predicates. In the above definition, the phrase “-freelyinferable” means that from the only facts
on the goal predicates an RIIA can generates some suppllementary predicat es.
denotes the set of weakly reducing FGS programs at most graph rewriting rules.
denotes the set of sizebounded FGS programs with at mostgraph rewriting rules. For constant $n\geq 1$ ,andhave infinitely many
hypotheses.
denotes the set of all
canonical wealky reducing FGS programswith just $m$ graph rewriting rules andpredicite symbols insuch that thesize of each rule is not greater than$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{i}_{\mathrm{C}}\mathrm{a}1- \mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}$$\mathcal{W}\mathcal{R}^{[\leq n]}$$n$$SB^{[\leq n]}$$n$$\mathcal{W}R^{[\leq n]}$$SB^{[\leq n]}$$\mathcal{M}\mathcal{W}\mathcal{R}^{[m]}[\Pi 0](s)$$\Pi_{0}$.

$\mathrm{h}\mathrm{e}\mathrm{a}\mathrm{d}’ \mathrm{s}s$

By the procedure RIIA-WR in Figure 3,
we have (1) of the following Theorem 1 and121

procedure
begin$RIIA_{-}WR(n, \mathrm{I}\mathrm{I}_{0})$$T=\emptyset;F=\emptyset$;$readxt_{ore}(\tau, F)$

4. Implementation of KD-FGS
and Experimental Results

;

;

while
do begin
output the empty FGS program;$read_{-}store(\tau, F)$ ;$T=\emptyset$

end;

We have implemented a prototype of the
KD-FGS system by constructing an FGS
interpreter and a refutably inductive inference algorithm in Common Lisp. The FGS
interpreter is an extension of the Prolog interpreter (P.
, Chap. 11).
In Table 1, we summarize 6of running KD-FGS on a DEC-Alpha compatible workstation (clock 500) withGCL2.2. In. and 2, input data arepositive and negative examples of TTSP
graph (see Figure 1). In. (resp.,$\mathrm{N}\mathrm{o}\mathrm{r}\mathrm{V}\mathrm{i}\mathrm{g}[6]$$\tau_{0=}T;F_{0}=F$

for $m=1$ to$n$;do begin$\mathrm{e}\mathrm{x}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{n}1e\mathrm{n}\mathrm{t}_{\mathrm{S}}$$s_{m}= \max\{||A|||A\in T_{m}-1\}$ ;$\mathrm{M}\mathrm{H}\mathrm{z}$recursively generat
and set it to ;for eachdowhile $(T,.F)$ is consistent with
do begin
output ;;end;$T_{m}=T;F_{m}=F$ ;end;
refute the classand stop;end;
procedure;
begin
read the next fact $(w,t)$ ;if $t=^{J}+’$ then $T=T\cup\{w\}$else $F=F\cup\{w\}$ ;end.

$e\mathcal{M}\mathcal{W}\mathcal{R}^{[m]}[\Pi_{0}](s_{m})$$S$$\Gamma\in S$,$\mathrm{E}\mathrm{x}\mathrm{p}$$1$$\mathrm{E}\mathrm{x}\mathrm{p}$$1$$M_{\Gamma}$$\mathrm{F}\mathrm{G}\mathrm{s}^{\mathrm{s}}\mathrm{P}^{\mathrm{r}}\mathrm{o}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{s}\mathrm{W}\mathrm{i}\mathrm{t}4_{\mathrm{e}}^{\mathrm{t}}2,\mathrm{h}\mathrm{e}\mathrm{h}\mathrm{y}\mathrm{p}\mathrm{o}\mathrm{t}\mathrm{h}e\mathrm{s}\mathrm{i}_{\mathrm{S},\mathrm{t}\mathrm{r}_{\mathrm{h}\mathrm{t}2(\mathrm{r}}}\mathrm{s}_{\mathrm{C}\mathrm{t}\mathrm{e}}\mathrm{p}\mathrm{a}\mathrm{c}ec11_{1\mathrm{e}_{\mathrm{S}}}\mathrm{e}\mathrm{t}\mathrm{o}\mathrm{f}\mathrm{a}11\mathrm{r}\mathrm{e}\mathrm{S}\mathrm{i}\mathrm{d}\mathrm{w}_{\mathrm{o}\mathrm{s}}e\mathrm{a}\mathrm{y}\mathrm{r}\mathrm{d}\mathrm{u}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{m}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{p},c_{2},)\mathrm{n}\mathrm{c}\mathrm{i}\mathrm{i}_{\mathrm{S}}\mathrm{e}\mathrm{P}\cdot 2\ovalbox{\tt\small REJECT}$$\Gamma$$\mathrm{r}e\mathrm{a}\mathrm{d}_{-^{\mathrm{S}}}\mathrm{t}\mathrm{o}\mathrm{r}\mathrm{e}(\mathrm{T},\mathrm{F})$$\mathcal{W}\mathcal{R}^{\llcorner<n]}$$\gamma ead_{Bt_{\mathit{0}}}re(\tau, F)$

Figure 3: RIIA-WR: a refutably inductive
inference algorithm for the classatoms in each body and at most 2 (resp., 3)
rules in each program, which is denoted by“#atom , #rule ” (resp., “#atom, #rule ”). After thereceives 3
positive and 5 negative examples, which isdenoted by “”, it refutesin. (resp., it converges to a correct FGS program infor TTSP graphsin. ). We confirm that the system isuseful for knowledge discovery from graphdata.
$\leq 2$

$2$

Theorem 1. (1)any, the classof all weakly reducing FGS programs with at most graph rewriting rules
isfreely and refutably inferable from complete data.
]of all. (2) For any $n>0$ , the classslze-bounded
pg.rams with at mostgraph rewriting rules theoretical-termfreely and refutably inferable from complete data.
$n\geq 0$$\mathrm{I}^{i^{\urcorner}}\mathrm{o}\mathrm{r}$$\mathcal{W}\mathcal{R}^{[\leq n]}$$n$$\leq$$\mathrm{s}\mathrm{y}_{\mathrm{S}\mathrm{t}}\mathrm{e}\mathrm{n}1$$\#\mathrm{p}\mathrm{o}\mathrm{s}=3,$$C_{1}$$\#\mathrm{n}\mathrm{e}\mathrm{g}=5$$1$$\mathrm{E}\mathrm{x}\mathrm{p}$$C_{2}$$\mathrm{E}\mathrm{x}\mathrm{p}$$2$5. Refutably Inductive Inference of NLC Graph Gram-mars$\mathcal{W}\mathcal{R}^{[\leq n]}$we have (2) by a similar procedure. The
proof of Theorem 1 is based on [5].

$\leq 2$$\leq 3$

FGS is a kind of graph generating system.
So we consider refutable inference of NLC
graph grammars.

Definition 3 ([3]).
A node-label controlled graph grammar(NLC graph grammar, for short) is a fivetuple $(\Sigma,N, P, S, c)$ , where$\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\mathrm{e}\mathrm{t}\mathrm{i}_{\mathrm{C}}\mathrm{a}1_{-\mathrm{t}\mathrm{m}}\mathrm{e}\mathrm{r}$$se^{[}\leq n$$\mathrm{F}\mathrm{G}^{-_{\mathrm{s}}}$$n$$1\mathrm{S}$1.

$\Sigma$

is a finite set of terminal labels,

2. $N$ is a finite set of nonterminal labels
with,$\Sigma\cap N=\emptyset$

3. $P$ is a finite set of productions eachproduction has the form $Xarrow\alpha$ ,where $X$ is a nonterminal label in $N$
and is a graph with a vertex label
inand an edge label in ,$\alpha$We can construct a machine discovery
system for a refutably inferable hypothesis
space. Thus the above Theorem 1 gives atheoretical foundation of the KD-FGS system.

$\Sigma\cup N$

4.

is a special nonterminal lab
the start symbol,$S$$\Lambda$$e1$called122

Table 1: Experimental results on the KD-FGS system5.

is a connection relation
A.

$C$$C\subseteq(\Sigma\cup$$N)\cross(\Sigma\cup N)\cross$

In this paper, we assume that in eachthe graph has at least
production
one vertex and no multiple edge. Let $G=$.
$Xarrow\alpha$$\alpha$$\mathrm{f}_{\mathrm{h}\mathrm{t}’}^{\Sigma,N}\mathrm{e}\mathrm{W}’\mathrm{a}\mathrm{y}\mathrm{t})P,$$s_{\mathrm{h}\mathrm{a}}c\mathrm{b}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{N}\mathrm{L}\mathrm{C}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{p}\mathrm{h}\mathrm{g}\mathrm{r}\mathrm{a}\mathrm{m}\mathrm{m}\mathrm{a}\mathrm{a}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}xarrow\alpha\mathrm{i}\mathrm{n}P\mathrm{i}\mathrm{r}\mathrm{s}$applied to transform a graph is as follows:
Step 1. Start with a graph and a specificoccurrence of an $X$ -node in . We call thisnode the mother node. The set of nodes
which are directly connected to the mothernode is denoted by Neighborhood.
Step 2. Delete the mother node and alledges incident to the mother node from thegraph , and call the resulting graph .
. Add to a copy of the labeledgraph . This new occurrence of is called
the daughter graph.
. For each pair $(Y, Z, L)$ in the connection relation, connect every Y-no de in
the daughter graph to every -node in
Neighborhood by the edge labeled with
$\mu$

$\mu$

$\mu’$$\mu$$\mu’$$St\mathrm{e}p\mathit{3}$$\alpha$$\alpha$$St\mathrm{e}p4$$Z$$L\in\Lambda$.

For example, the NLC graph grammar$G=(\{a\},$ $\{A\},$ $\{Aarrow\alpha, Aarrow\beta\},$ $A,$ $\{(A$ ,$(a,a, a)\})$ can generate the set of allcomplete graphs [2], whereis a graphconsisting of one vertex labeled with andis a graph consisting of two vertices labeled with and , respectively, and oneedge labeled with between them.
$a,$ $a),$$\alpha$$a$$\beta$

$A$

$a$

$a$

Theorem 2. For any $n\geq 0$ , the classof all NLC grap. grammars with at mostproductions refutably inferable fromcomplete data.
$\mathrm{h}$$n$$1\mathrm{S}$a knowledge discovery system from graphdata. We also consider refutable inferenceof NLC graph grammars.

References[1] S. Arikawa, T. Shinohara, and A. Yamamoto. Learning elementary formal
systems. Theoretical Computer Science 95:97-113, 1992.
[2] A. Ehrenfeucht, M.
Main, and
G. Rozenberg. Restrictlons on NLC
graph grammars. Theoretical Com$\mathrm{G}_{:}$. On
the structure ofgraph languages. Information Sciences, 20.191-216, 1980.
[4] S. Muggieton and D. Page. Special issue on inductive logic programming. Machine Learning, $26(2-3):97-$
252 1997.
[5] Y.
ukouchi and S. Arikawa. Towards a mathematical theory of machine discovery from facts. Theoretical[3]$6u.te\mathrm{J}\mathrm{a}\mathrm{n}rS\mathrm{s}^{C}\mathrm{s}\mathrm{e}n\mathrm{s}ienCe,3\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{G}.\mathrm{R}\mathrm{o}\mathrm{z}\mathrm{e}\mathrm{n}1:211-223,1\mathrm{b}\mathrm{e}984\mathrm{r}\mathrm{g}.$$\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}- 1\mathrm{a}\mathrm{b}\mathrm{e}1_{\mathrm{C}}- \mathrm{o}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{o}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{d}$$\dot{\mathrm{M}}$[6]$\mathrm{p}^{O}.\mathrm{N}_{\mathrm{o}\mathrm{r}\mathrm{v}}\mathrm{i}\mathrm{g}.P^{C}a^{\dot{i}}radCmputerSenc_{i}e,137\cdot 5384gmsofA^{-}rtiticial\dot{I}n-1995$

telligence Programming: Case Studies
in Common Lisp. Morgan Kaufmann,
1992.
[7] T. Shinohara. Rich class inferablefrom positive data: length-bounded
elementary formal systems. Information and Computation, 108:175-186,

1994.

[8] T.Uchida,T.Shoudai,and S.Miyano.
Parallel algorithm for refutation tree
problem on formal graph systems. IEICE Transactions on Information and[9]$\mathrm{A}.\mathrm{Y}\mathrm{a}\mathrm{m}\mathrm{a}s_{y_{St\mathrm{E}78}-}ems,\mathrm{m}\mathrm{o}\mathrm{t}\mathrm{o}.\cdot \mathrm{D}\mathrm{b}_{\mathrm{r}\mathrm{o}\mathrm{C}}^{2}).\cdot 99-11295.\mathrm{t}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{i}_{\mathrm{s}\mathrm{e}\mathrm{m}}^{19}\mathrm{a}\mathrm{n}\mathrm{i}_{\mathrm{C}}\mathrm{s}$and negativeof elementary formal system. Journal of Logic$1\mathrm{n}\mathrm{f}_{\mathrm{o}\mathrm{r}\mathrm{m}}\mathrm{a}\mathrm{t}\mathrm{i}_{\mathrm{o}\mathrm{n}}$6. Conclusion
We show that sufficiently large hypothesis spaces of FGS ograms are refutably
inferable and thus
a theoretical foundation of the KD-FGS system, which is$\mathrm{p}.\mathrm{r}$$\mathrm{g}_{1}\mathrm{v}\mathrm{e}$[10]. Inductive inference by stepwise palr expansion. Journal of Jpn. Soc. Artif. Intell., $12(1):58-67$ , 1997.
$\mathrm{K}.\varphi^{r}Pro\mathrm{o}\mathrm{s}\mathrm{h}\mathrm{i}\mathrm{d}\mathrm{a}\mathrm{a}amming,\mathrm{l}3\cdot 89-98,199\mathrm{n}\mathrm{d}\dot{\mathrm{H}}.\mathrm{M}_{\mathrm{o}\mathrm{t}_{\mathrm{o}\mathrm{d}\mathrm{a}}}2.$