数理解析研究所講究録
1489 巻 2006 年 64-70

64

[10]

Learning of Elementary Formal Systems with Two Clauses
using Queries and Their Languages
加藤浩軸

Hirotaka Kato
東海大学大学院理学研究科数理科学専攻

Graduate School of Science, Tokai University, Hiratsuka 259-1292, Japan松本哲志

Satoshi Matsumoto
東海大学理学部情報数理学科

Department of Mathematical Sciences, Tokai University, Hiratsuka 259-1292, Japan{hirotaka,$\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{u}\mathrm{m}\mathrm{o}\mathrm{t}\mathrm{o}$}$\mathrm{Q}\mathrm{s}\mathrm{s}.\mathrm{u}-\mathrm{t}\mathrm{o}\mathrm{k}\mathrm{a}\mathrm{i}.\mathrm{a}\mathrm{c}.\mathrm{j}\mathrm{p}$宮原哲浩

Tetsuhiro Miyahara
広島市立大学情報科学部知能情報システム工学科

Faculty of Information Sciences, Hiroshima City University, Hiroshima 731-3194, JapanmiyaharaQits. hiroshima-cu. . jp$\mathrm{a}\mathrm{c}$Abstract

model, in general.

An elementary formal system, EFS for short, is akind of logic program over strings, and regarded
as a set of rules to generate a language. For an
denotes the set of all
EFS , the language
strings generated by F. Many researchers studied the learnability of EFSs in various learningmodels. In this paper, we introduce a subclass, and study the learnof EFSs, denoted byin the exact learning model. The
ability ofcontains the class of regular patterns,
classwhich is extensively studied in Learning Theory.
. In
be a target EFS of learning inLetthe exact learning model, an oracle for superset
queries answers “yes” for an input EFS in, and outputs a string
is a superset ofif
in $L(\Gamma.)-L(\Gamma)$ , otherwise. An oracle for membership queries answers “yes” for an input string,, and answers “
ifis included inotherwise.
is exactly idenWe show that any EFS in
tifiable in polynomial time using membership andsuperset queries. Moreover, for other types ofqueries, we show that there exists no polynoby using
mial time learning algorithm forthe queries. This result indicates the hardness
in the exact learningof learning the class$r\epsilon \mathcal{P}S$$r\epsilon \mathcal{P}S$$r\epsilon\pi$$r\mathcal{E}\mathcal{F}S$$\Gamma_{*}$$\Gamma$$L(\Gamma)$

$w$

$w$

1

Introduction$L(\Gamma)$$\Gamma$$r\epsilon FS$$L(\Gamma_{*})$$no^{)}’$$L(\Gamma_{*})$$rS\mathcal{P}S$$r\mathcal{E}FS$$r\mathcal{E}FS$An elementary formal system, EFS for short, isa kind of logic program which directly manipulates strings, and is regarded as a set of rules togenerate a language. A pattern is a nonempty finite string of constant symbols and variables. In
EFSs, patterns are used as terms in a logic program. A rule (or definite clause) in EFSs is aclause of the form $Aarrow B_{1,)}\ldots B_{m}(m\geq 0)$ ,are atoms. Learning of rules
where $A,$
from string data is important in machine learning[1] and it can be applied to learning of rules fromHTML files since HTML files are considered to bestring data. Learning of EFSs has been long studLearning Theied inory [4, 8, 10, 11]. The purpose of this work is to
give a new learnability of EFSs.
Consider examples of EFSs defined as follows.
Let be a unary predicate symbol, and conand variables. $p(ab)arrow$ andstant symbols,$p(axb)arrow p(x)$ are examples of rules.
$\{p(ab) arrow, p(axb)arrow p(x)\}$ is an example of
EFS consisting of the above two rules. EFSs
$B_{1},$$\cdots,$$B_{m}$$\mathrm{A}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{m}\mathrm{i}\mathrm{c}/\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{u}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}$

$a$

$p$

$x$

$b$

$y$

$\Gamma_{1}=$65
and F3are definedsimilarly. The language
generated by an
EFS is the set of all constant strings by substituting non-empty constant symbols for variables and applying Modus Ponens to rules in
F. Let $\Sigma=\{a, b, c\}$ be a finite alphabet. In
the above examples, $L(\Gamma_{1})=\{a^{n}b^{n}|n\geq 1\}$ ,$L(\Gamma_{2})=\{a^{n}wb^{n}|w\in\Sigma^{+}, n\geq 1\}$ , and$\Gamma_{2}=\{p(axb)arrow, p(ayb)arrow p(y)\}$$=$$\{p(axb)arrow, p(aybzc)arrow p(y),p(z)\}$$L(\Gamma)$$\Gamma$$L(\Gamma_{3})=${ $aab,$ $abb,$ $acb$ , aaabbaabc, aabbbaabc, . . .}.

In this paper, we give a polynomial time learning algorithm fora subclass of EFSs in the exact
learning model. The framework of EFSs for studying formal language theory was established by [3]and the unifying framework of language learning
using EFSs was originated by [4]. A pattern is regular if each variable appears in the pattern at mostonce. The target class of learningin this paper is defined as the set of EFSs which satisfy
the following two conditions. (1) All patterns in
the heads of all definite clauses in are regular.
(2) consists of one or two definite clauses of theform $p(\pi)arrow$ , or exactly two definite clauses of theforms $p(\pi’)$ -and $p(\tau)arrow p(x_{1}),$ $\cdots,p(x_{n})$ , whereis a unary predicate symbol,, $x_{n}(n\geq 1)$
are all of the variables appearing in , and contains at least one variable. By the definition, theclasses of regular patterns and unions of two regular patterns are included in. In the above
examples,is not in $r\varpi$ since the pattern $ab$
contains no variable.
and.
are inLetbe an EFS in
to be identified by alearning algorithm, and we say that the EFS
isa target. We introduce the exact learning model
via queries due to Angluin [2]. In this model,
learning algorithms can access to oracles that answer specific kinds of queries about the unknown
language. We mainly consider the following two oracles in this paper. (1) Superset oracle:
The input is an EFS in,. Ifthen the output is “yes“. Otherwise, it returns
a counterexample $t\in L(\Gamma.)-L(\Gamma)$ . The queryis called a superset query. (2) Membership ora$cle$ : The input
is a string in. The output
is “yes” if, and “ $no’$’ otherwise. The
query is called a membership query. A learningalgorithm $A$ collects information about
byusing queries and outputs an EFS in. We
say that a learning algorithm $A$ exactly identifies atargetin polynomial time using a certain typeof queries if $A$ halts in polynomial time and outputs an EFS
such thatusing queries of the specified type.
We discuss the related works of this work. A
pattern
is regarded as a very restricted form$\mathrm{r}\mathit{8}\mathcal{P}S$$\Gamma$$\Gamma$$\Gamma$$P$$x_{1},$$\cdots$$\tau$$\pi’$. Angluin [1] originated the research of pattern learning under another learning model of inductive inference, which
is an infinite process of learning. Angluin also
showed that patterns are exactly learnable in polynomial time using restricted superset queries [2].
We showed that regular patterns are exactly learnable in polynomial time using membership queries
and a positive example [5]. We showed that finite unions of subsequences are exactly learnable
in polynomial time using membership and equivalence queries [6]. Moreover, we showed that finite unions of tree patterns are exactly learnable inpolynomial time using restricted subset and equivalence queries [7].
The paper [10] deals with a class of restricted
EFSs (called primitive EFSs), which is similar but, under the learning model
incomparable toof inductive inference of positive examples without
allowing empty string to be substituted for variables. The paper [11] extended this learnability byallowing empty string to be substituted for variables. The work [8] deals with a class of EFSs under the exact learning model using equivalence andextensions of membership queries. The work [8] is
known so far about the learnability of EFSs underexact learning model.
of EFS $\{p(\pi)arrow\}$ in$r\mathit{8}FS$$r\epsilon n$$r\mathit{8}\hslash \mathrm{S}$$\Gamma_{1}$$\Gamma_{2}$$r\mathcal{E}\mathcal{P}S$$\Gamma_{*}$$\Gamma_{*}$$L(\Gamma_{*})$$\Gamma$$r\mathit{8}\mathcal{F}S$$t$$L(\Gamma)\supseteq L(\Gamma_{*})$$\Sigma^{+}$$t\in L(\Gamma_{*})$$L(\Gamma_{*})$$\Gamma$$r\mathcal{E}\mathcal{F}S$$\Gamma_{\mathrm{r}}$$\Gamma\in r\mathcal{E}FS$

$\pi$

2

Preliminaries$r\epsilon \mathcal{P}S$$\Gamma_{3}$$L(\Gamma)=L(\Gamma_{\mathrm{s}})$Let be a finite set. We denote by
the numberof elements in . Let be a finite alphabet, $X$ a
countable set of vart ables, and II a set of predicate
symbols. We assume thatand these sets
$X$ andare mutually distinct. Each predicate
symbol is associated with a positive integer called
arity. Let
be a string. We denote bythelength of . We denote by $w[i]$ the i-th symbol instring , and by $w[i:j]$ the substringof . We define $w[i:j]=\epsilon$ (empty string) if $i>j$ .
For convenience, a prefix $w[1 : i]$ is abbreviatedas $w[:i]$ , and a suffix $w[i : |w|]$ as $w[i$ : , where$1\leq i\leq|w|$ . For a nonempty set, letdenotethe set of all nonempty strings.
.
A pattern is a nonempty string overIn particular, we say that a pattern is regudar
if each variable in appears at most once. An,
atom is an expression of the form
where is a predicate symbol with arity andare patterns. A definite clause is a
$B_{m}(m\geq 0)$ ,clause of the form $Aarrow B_{1},$where $A,$
are atoms. The atom isthe body
called the head and the partof the definite clause.
$S$

$|S|$

$S$

$\Sigma$$|\Sigma|\geq 2$$\Pi$$\Sigma,$

$|w|$

$w$

$w$

$w[i]\cdots w\mathrm{b}]$

$w$

$w$

$]$

$\Delta^{+}$$\Delta$$\Sigma$$\cup X$

$\pi$

$\pi$

$p(\pi_{1}, \cdots , \pi_{n})$

$n$

$p$

$\pi_{1},$$\cdots,$$\pi_{n}$$\cdots,$$B_{1},$$\cdots,$$A$$B_{m}$$B_{1},$$\cdots,$$B_{m}$

66
Definition 1 An elementary formal system, EFS
for short, is a finite set of definite clauses. For an
EFS , each definite clause in is called an axiom$\Gamma$$\mathrm{o}\mathrm{f}\Gamma$$\Gamma$.

in . In particular, a language
is a regularpattern language if $L=L(\Gamma,p)$ for some EFS$\{p(\pi)arrow\}$ , whereis a regular pattern.
Letbe the set of all regular langauges. Let
be the set of all EFS languages by EFSs in$L$$\Gamma$$p$$\Gamma=$$\pi$$\mathcal{R}$$r\Omega \mathrm{i}FS$

is a homomorphism from patterns to patterns such that $\theta(a)=a$ for eachand each variable is replaced with any patterns.
By , we denote the image of a pattern by a
substitution . For an atom $A=p(\pi_{1}, \cdots, \pi_{n})$ and, we define $A\theta=$
a clause $C=Aarrow B_{1},$A substitution$\theta$$a\in\Sigma$$\pi\theta$$\pi$$\theta$$\cdots,$$B_{m}$.
and,For patterns and we introduce binary relafollows:iffor someif. If
substitution , andand, then we write.
andLet be a pattern, $i(1\leq i\leq|\pi|)$ a positive
integer, and a symbol in . We denote by
the string obtained from by replacingwith, that is, $\pi_{1,q}=\pi[:i-1]\alpha\pi[i+1:]$ .
For a pattern , we denote by
the set of all
strings which are obtained from by replacing all
variables with a string of length 1. For a nonempty
set of Patterns, we define.
Let $T,T’$ be nonempty sets of patterns. We write! $T’$ if for any pattern $\pi\in T$ , there is a pattern$\pi’\in T’$
,
. If
and
such thatthen we write : $T’$ .
A definite clause is provable fhom an EFS ,, if is obtained by finitely many
denoted byapplications of substitutions and Modus Ponens asin the way of usual logic programming. We define
the language $L(\Gamma,p)=\{w\in\Sigma^{+}|\Gamma\vdash p(w)\}$ ,where is a unary predicate symbol.
$C\theta=A\thetaarrow B_{1}\theta,$$p(\pi_{1}\theta, \cdots,\pi_{n}\theta)$$\pi$$\pi\equiv\tau$$\pi\preceq\tau$$\tau\preceq\pi$$\tau\prec\pi$$\tau\not\geq\pi$$\tau\preceq\pi$$\pi=r\theta$$\pi\preceq\tau$$\pi$$\Sigma$$\alpha$Example 1 Let $\Gamma=\{p(axa)arrow, p(byb)arrow p(y)\}$ .
By the definition ofis in. But,
is not a regular language.
$r\mathcal{E}FS,$

Lemma 1

$rae\mathcal{P}S\not\subset$$r\mathcal{E}FS$$\Gamma$$L(\Gamma)$

R.

Example 2 Let be a constant symb and $L=$$\{a, aa, aaa\}$ . Then, it is clear thatis a regular
language. But, there exists no EFS in
with
$o1$

$a$

$L$

$rSr\mathfrak{F}$$\Gamma$$L(\Gamma)=L$.

Lemma 2$\mathcal{R}\not\subset ra\mathcal{P}S$.

crs are$\pi_{i,\alpha}$$\pi[i]$$\pi$$\alpha$$S_{1}(\pi)$

$\pi$

$\pi$

$P$

$S_{1}(P)= \bigcup_{\pi\in P}S_{1}(\pi)$$T$$\pi\preceq\pi’$$T\subseteq T’$$\tau \mathrm{Z}T’$

$T$

$C$

$\Gamma\vdash C$$\Gamma$$C$$p$Deflnition 2 We denote by $rm$ the set of EFSs
which satisfy the following conditions:$\Gamma$

1. All patterns in the heads of all clauses inare regular.

2.

.

$B_{m}\theta$$\tau$$\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\preceq \mathrm{a}\mathrm{n}\mathrm{d}\equiv \mathrm{a}\mathrm{s}$$\theta$$\cdots,$$r\mathcal{E}FS$$r\mathcal{E}FS$$\Gamma$$p$$\cdots,$$\tau$$\pi’$$p$$\Gamma$$L(\Gamma’,p)\subseteq L(\Gamma,p)$$\Gamma’\subsetneq\Gamma$,
In this paper, since we deal with the class
we fix a unary predicate symbol, say , and denotebysimply. We denote by(resP.,) an EFS $\Gamma=\{p(\pi)arrow$, $p(\tau)arrow p(x_{1}),$(resp., $\Gamma=\{p(\pi)arrow\}$ ,$r\epsilon FS$$p$$L(\Gamma,p)$$L(\Gamma)$$\Gamma=(\pi, \tau)$$\Gamma=\{\pi\},$ $\Gamma=\{\pi,$ $\tau\}$$\cdots,p(x_{n})\}$. Moreover, by$\Gamma=\{p(\pi)arrow, p(\tau)arrow-\})$(resp.,$L(\{\pi\}),$, $p(\tau)arrow p(x_{1}),$$\cdots$$L((\pi,\tau))$) we denote, $p(x_{n})\})$ (resp., $L(\{p(\pi)$ -} ,$L(\{\pi,$ $\tau\})$$L(\{p(\pi)arrow, p(\tau)arrow\}))$$L(\{\mathrm{p}(\pi)arrow$$)$.

, we define the following particularpattern{ $xj=\pi|x$ appears in }, where
all variables substituted to the variables in aretaken to be distinct, so
is always regular. It isclear thatis defined in asimilar way.
Let
be an EFS in
allof the variables appearing in .
is recursively
defined as follows:
and for any positive$:=$
integer $t\geq 2,$$\zeta_{n}\}|\zeta_{1}\in\Gamma_{[t-1]}\cup\{\pi\},i=1,$ $\cdots,n\}$ .
We define. Note that is not included in .
Thus,
) Si $L((\pi, \tau))$A primitive EFS , a PFS for short, is definedin [11] as follows:

For$\Gamma=(\pi, \tau)$$\tau_{\pi}=\tau$$\tau$$\tau$$\tau_{\pi}$.

$\tau_{\tau}$$\Gamma=(\pi, \tau)$consists of one or two clauses of the form$p(\pi)arrow$ , or exactly two clauses of the forms$p(\pi’)arrow$ and $p(\tau)arrow p(x_{1}),$ $\cdots,p(x_{n})$ , where$x_{n}(n\geq$
is a unary predicate symbol,
1) are all of the variables appearing in , andcontains at least one variable.

$r$Deflnition 3 Let
be an EFS inanda unary predicate symbol appearing in F.
isreduced if.
for any$|\pi|\leq|\tau_{\pi}|\leq|\pi||\tau|$$\Gamma$$\Gamma$$x_{1},$

The above lemmas show that $R$ andincomparable.

.

$r\mathit{8}\mathcal{P}S,$$x_{1},$$\cdots,x_{n}$$\Gamma_{[t|}=\Gamma_{[t-1]}\cup\{\tau\{x_{1}:=\zeta_{1},$$\cdots,x_{n}$$\tau$$\Gamma_{[t]}$$\Gamma_{[1|}=\{\tau_{\pi}\}$$\Gamma_{\tau}=\bigcup_{t>1}\Gamma_{[t]}$.

$L\overline{(}\Gamma_{\tau}$$\pi$$\Gamma_{\tau}$$\Gamma$

By the definition, the class of regular patterns
and unions of two regular patterns are included in. We define the size of , denoted by , asfollows: (1). $|\Gamma|=|\pi|$ if $\Gamma=\{p(\pi)arrow\},$ (2).
if $\Gamma=\{p(\pi_{1})arrow, p(\pi_{2})arrow\},$ (3).
$r\epsilon\approx$$\Gamma$$|\Gamma|$$|\Gamma|=$$|\pi_{1}|+|\pi_{2}|$$|\Gamma|=$

if $\Gamma=\{p(\pi)arrow, p(\tau)arrow p(x_{1}), \ldots,p(x_{n})\}$ .
A language is an $EFS$ language if $L=L(\Gamma,p)$for some EFS and some unary predicate symbol$|\pi|+|\tau|$$L$$\Gamma$

1. All patterns in heads of all clauses inregular.

2.

$\Gamma$areconsists of exactly two clauses of the foms$p(x_{n})$ , where–and $p(\tau)arrow p(x_{1}),$is a unary pr\’eicate symbol, andare all of the variables appearing in .

$\Gamma$$p(\pi)$$p$$\cdots,$$x_{1},$ $\cdots,$ $x_{n}$$\tau$

67
An EFS in
is different from a PFS. In caseof erasing patterns, Uemura et al. showed the following theorem in [11].
$r\mathcal{E}FS$Theorem 1 [11] Let
be a PFS. The
following statements are equivalent: (i)is reduced. (ii)
, whereProcedure LENGTHI
Given: An oracle
for the target
begin$S\mathrm{u}p_{\Gamma}$$\Gamma=(\pi, \tau)$$\bigcup_{\zeta\in\Gamma_{\tau}}L(\zeta)$.

$L(\pi)\cap L(\Gamma_{\tau})=\emptyset$

The theorem holds for any EFS
in case of nonerasing patterns.

$\Gamma=(\pi, \tau)$

Corollary 1 Let
be an EFS in
The following statements are equivalent: (i)reduced. (ii)
, where$\Gamma=(\pi, \tau)$$\bigcup_{\zeta\in\Gamma_{\tau}}L(\zeta)$

3

.

while

$S\mathrm{u}p_{\Gamma},(\{x_{1}\cdots x_{\ell+1}\})=$$\ell:=\ell+1$

in$r\mathcal{E}\mathcal{P}S$$r\epsilon \mathcal{F}S$$L(\pi)\cap L(\Gamma_{\tau})=\emptyset$$\Gamma$.

is$L(\Gamma_{\tau})=$is a regular pattern“yes“ do$//x_{1}\cdots x_{\ell+1}$$L(\Gamma_{\tau})=$$\Gamma_{*};$;$\ell:=1$$\Gamma$.

;

output ;end.
$t$Procedure LEARNPI
Input: A positive integer with
Given: An oracle
for the target$(\ell)$$S\mathrm{u}p_{\Gamma}$

begin

;

$\Gamma_{*};$

is a regular pattern$//x_{1}x_{2}\cdots x_{\ell}$Learning model.

$\ell=|\pi_{*}|$$\ell$.

$\pi:=x_{1}x_{2}\cdots x_{\ell)}$

for $i:=1$ to

In this paper, letbe an EFS in
to be
identified, and we say that the EFS
is a target.
Non-reduced EFSs have redundant axioms. Even
if we consider only reduced EFSs, the expressive
power of EFSs is same. So we assume that target$r\mathcal{E}FS$$\Gamma_{*}$$\Gamma_{*}$EFSs are reduced.

We introduce the exact learning model via
queries due to Angluin [2]. In this model, learning algorithms can access to oracles that answer
specific kinds of quer es about the unknown lan-foreach$\ell$

do begin
do begin$\alpha\in\Sigma$;
if $Sup_{\Gamma}.(\{\pi’, x_{1}\cdots x_{\ell+1}\})=$ “yes“
then begin$\pi:=\pi’$ ;break;
end;
end;
end;
output ;end.
$\pi’:=\pi_{i,\alpha}$

$\pi$

$i$

guage

$L(\Gamma_{*})$. We consider the following oracles.

(1). Superset oracle: The input is an EFS
in. If, then the output
is “yes”. Otherwise, it returns a counterexample $t\in L(\Gamma_{*})-L(\Gamma)$ . The query is called asuperset query. (2). Subset oracle Subr.: The. If
inPut is an EFS in,then the output is “yes“. Otherwise, it returns
a counterexample $t\in L(\Gamma)-L(\Gamma_{*})$ . The queryis called a subset query. (3). Membership ora: The input is a string in. The
output is “yes” if $t\in L(\Gamma_{*})$ , and “no” otherwise. The query is called a membership query.
(4). Equivalence oracle: The input is an
EFS in. The output is “yes” if $L(\Gamma)=$. Otherwise, it returns a counterexample$t\in(L(\Gamma)-L(\Gamma_{*}))\cup(L(\Gamma_{*})-L(\Gamma))$. The queryis called an equivalence query.
A learning algorithm $A$ collects information
about
by using queries and output an EFS
in. We say that a learning algorithm $A$$exacu_{y}$identifies a target F. in polynomial timeusing a certain type of queries if $A$ halts in polynomial time with respect to F. and outputs an EFS
such that $L(\Gamma)=L(\Gamma_{*})$ using queries ofthe specified type.
$S\mathrm{u}p_{\Gamma}.$$\Gamma$$r\epsilon \mathcal{P}S$$\Gamma$$r\mathcal{E}FS$$cle\mathrm{M}\mathrm{e}\mathrm{m}_{\Gamma}.$$r\mathit{8}\mathcal{P}S$$L(\Gamma_{*})$

4

Learning of restricted EFSs
using Queries$L(\Gamma)\subseteq L(\Gamma_{n})$$t$$E\mathrm{q}\mathrm{u}i\mathrm{v}_{\Gamma}.$$\Gamma$Figure 1: Procedure LENGTHI and LEARNPI$L(\Gamma)\supseteq L(\Gamma_{*})$$\Sigma^{+}$.

be a target EFS in. Then we consider the following cases: (i).
. (ii).
and the length ofF.
is the same as, that is,. (iii). F.
andthe length ofis not the same as , that is,. Without loss of generality, we assume

Let$\Gamma$$rS\mathcal{F}S$$\Gamma_{*}=\{\pi_{*}\}$$=\{\pi_{*},\tau_{*}\}$$\pi_{*}$$|\pi_{*}|=|\tau_{*}|$$\tau_{*}$$=\{\pi.,\tau_{*}\}$$\pi_{*}$$\tau_{*}$$|\pi_{*}|\neq|\tau_{*}|$$|\pi_{*}|<|\tau_{*}|$.

$(\mathrm{i}\mathrm{v})$.

$\Gamma_{*}=(\pi_{*}, \tau_{*})$.

is in the cases (i), (ii) or (iii), we canregardas a set of at most two regular patterns.
Since we use Theorem 2 for some lemmas and theorems, we assume
in this paper.

When$\Gamma_{*}$$\Gamma_{*}$$|\Sigma|\geq 5$$L(\Gamma_{*})$$\Gamma$$t\epsilon\approx$$|$$\Gamma\in r\mathcal{E}FS$Theorem 2 [9] Suppose $|\Sigma|\geq 2k+1$ . Let bea nonempty finite set of regular patterns, a setof at most regular patterns. Then the following$(2)$
three statements are equivalent: (1)
$P$

$Q$

$k$

$P\subseteq Q,$$L(P)\subseteq L(Q),$(3)$S_{1}(P)\subseteq L(Q)$.

68

Procedure LEARNPI-TAUl
Input: A regular pattern satisfying
Condition A andGiven: An oracle
for the target

Procedure LEARNPI-TA $U2(\pi’, \tau’)$Input: Regular patterns
andsatisfying Condition B-2 for ,where satisfies Condition ;Given: An oracle
for the target
begin$\pi’’:=\pi’;i:=1$ ;while $(i\leq|\pi’’|)$ anddo$i:=i+1$ ;while $i\leq|\pi’’|$ do begin
foreachdo begin
if“yes” thenbegin
; break;$(\pi)$$\pi’$$\pi$;$L(\Gamma_{*})\subseteq L(\{\pi\})$$Sup_{\Gamma_{*}}$$\pi$$\Gamma_{*};$

$\pi$

begin

$S\mathrm{u}p_{\Gamma}$;
while (
$i_{\pi}:=1$$(i_{\pi}\leq|\pi|)$while
foreachand) do$(\pi[i_{\pi}]\in\Sigma)$;$i_{\pi}:=i_{\pi}+1$$i_{\pi}\leq|\pi|$;$\Gamma_{*};$$\alpha\in\Sigma$

whileforeach$i_{\tau}\leq|\pi|$do begin
do begin;$S\mathrm{u}p_{\Gamma}.(\{\pi_{\dot{\iota},\alpha}’’,\tau’\})=$$\beta\in\Sigma$$\pi’:=\pi_{l_{\pi},\alpha}$$\pi’’:=\pi:_{r},\beta$if.

$\mathrm{B}$$(\pi’’[i]\in\Sigma)$

do begin
do begin$\alpha\in\Sigma$$i_{\tau}:=i_{\pi}$$\tau’$$\pi’’:=\pi_{1\alpha}’’.,$;“yes“ then$S\mathrm{u}p_{\Gamma}.(\{\pi’, \pi’’\})=$

begin
outputend;$\pi’,$$\pi’’$; halt;end;$i_{\tau}:=i_{\tau}+1$

while (;$(i_{\tau}\leq|\pi|)$$i_{\tau}:=i_{\tau}+1$

and$(\pi[i_{\tau}]\in\Sigma)$

) do

end;
end;
$i:=i+1$ ;while $(i\leq|\pi’’|)$ and $(\pi’’[i]\in\Sigma)$ do$i:=i+1$ ;end;$7”.:=\tau’;i:=1$ ;while $(i\leq|\tau’’|)$ anddo$i:=i+1$ ;while
do begin
foreachdo begin
if
then
begin
; break;
end;
end;$i:=i+1$ ;while $(i\leq|\tau’’|)$ anddo$i:=i+1$ ;end;
output;end.
$(\tau’’[i]\in\Sigma)$

;

end;
end;

$i\leq|\tau’’|$$\alpha\in\Sigma$$i_{\pi}:=i_{\pi}+1$

while (;$(i_{\pi}\leq|\pi|)$$S\mathrm{u}p_{\Gamma}.(\{\pi’, \tau_{*,\alpha}’’.\})=^{l}’ yes’’$and$(\pi[i_{\pi}]\in\Sigma)$) do$i_{\pi}:=i_{\pi}+1,\cdot$$\tau’’:=\tau_{\mathrm{t},\alpha}’’$end;
output “no”;
end.

$(\tau’’[i]\in\Sigma)$

Figure 2: Procedure LEARNPI-TAUl

For a regular pattea , we define the following
three conditions.
$\pi$

Condition :
$A$

A-l

$\pi$

satisfies$|\pi|$$=$$|\pi_{*}|$and$L(\Gamma_{*})$$L(\{\pi’,x_{1}x_{2}\cdots x_{|\pi|+1}\})$$\pi’$

C-2 There is a regular pattern satisfying
the following conditions for :C-2-1 There is a shortest string $w\in$$L(\Gamma_{*})-L(\{\pi\})$ such that $|w|=|\tau|$
and
.
C-2-2
.
There is no regular pattern ‘such that $|\tau’|=|\tau|,$and$L(\{\tau\})\subseteq L(\Gamma_{*})$$\mathrm{C}-2-3$$\tau$$\tau’$$\pi’\prec\pi,$ $\tau’\prec\pi$:$L(\Gamma_{\mathrm{r}})\not\subset$, and$w\preceq\tau$$L(\Gamma_{*})\subseteq$$C$satisfies Condition A and$\tau$:$L(\Gamma_{*})\subseteq L(\{\pi’, \tau’\})$

$\pi$

$\pi$

$\pi$

$\pi’$

Condition

such$L(\Gamma_{*})\subseteq$

for .

$\pi$

C-l

$L(\{\pi\})$satisfies Condition A and$L(\{\pi\})$ , and
B-2 There are regular patterns andthat $|\pi’|=|\tau’|=|\pi|,$
for .

B-l

$\subseteq$, and

A-2 There is no regular patternthat $|\pi’|=|\pi|,$ $\pi’\prec\pi$ and$B$$\tau’’$

Figure 3: Procedure LEARNPI-TAU2$L(\{\pi, x_{1}x_{2}\cdots x_{|\pi|+1}\})$

Condition$\pi’’,$

suchand$\tau\prec\tau’$$L(\{\tau’\})\subseteq L(\Gamma_{*})$

.

$\pi$

By using the above conditions, Corollary 1 andTheorem 2, we can show the following theorem.

69

Procedure $LENGTH2(\pi)$Input: A regular pattern satisfying
Condition A andGiven: An oracle
for the target$\pi$$S\mathrm{u}p_{\Gamma}$

begin

.

Procedure LEARN-TA $U2(\pi, \tau)$
Input: Regular patterns andsuch that satisfies Condition ,satisfies Condition C-2 for ,and
SZ $L(\{\pi, \tau\})$ ;begin$\tau’:=\epsilon;i:=1;j:=1$ ;while $j\leq|\tau|-|\pi|+1$ do begin: $j+|\pi|-1$ ];ifthen begin$\tau’:=\tau’\tau[i : j-1]x_{j}$ ;$i:=j+|\pi|$ ;$j:=j+|\pi|$ ;end else begin$:=j+1$ ;
end;
end;
;
output ;$\pi$$L(\Gamma_{*})\not\leqq L(\pi)$;$\Gamma_{*}$$\mathrm{C}$$\tau$$\pi$$L(\Gamma_{*})$$t:=|\pi|+1$ ;$//x_{1}\cdots x_{\ell+1}$

while$S\mathrm{u}p_{\Gamma},$

is a regular pattern.
“yes” do$(\{\pi, x_{1}\cdots x_{\ell+1}\})=$$\ell:=\ell+1$ ;Let be a counterexample obtainedby the oracle;
output ;end.

$\pi’:=\tau \mathrm{b}$$w$$\pi\equiv\pi’$$S\mathrm{u}p_{\Gamma}.$$w$

Procedure LEARN-TAUl $(\pi,w)$$j$

Input: A regular pattern satisfying
Condition A andSZ $L(\{\pi\})$ , anda shortest string $w\in L(\Gamma_{*})-L(\{\pi\})$ ;Given: An oracle
for the target
begin$\tau:=w$ ;for $i:=1$ todoforeachdo
if $w[i]\neq\alpha$ thenif“yes” then
if
then begin$\tau[i]:=x_{i}$ ; break;end;
output, ;
end.
$\pi$

$L(\Gamma_{*})$$Me\mathrm{m}_{\Gamma}$.

$\Gamma_{*};$$\tau’:=\tau’\tau \mathrm{b}:]$$\tau’$

end.
Figure 5: Procedure LEARN-TAU2$|w|$$\alpha\in\Sigma$$M\mathrm{e}\mathrm{m}_{\Gamma_{*}}(w_{i,\alpha})=$$w_{i,\alpha}\not\in L(\pi)$$\tau$

Figure4:

LEARN-TA UIProcedure

LENGTH2$L_{i}$

Theorem 4 Any learning algorithm that exactly
identifies all strings of length using equivalence,
membership and subset queries must make at least$5^{n}-1$ queries in the worst case.
$n$6$\Gamma\in r\mathcal{E}FS$$O(|\Gamma_{*}|^{4})$$O(|\Gamma_{*}|^{2})$$O(|\Gamma.|^{2})$each of the hypotheses using equivalence, membership, and subset queries must at least $N-1$
queries in the worst case.

andTheorem 3 The algorithm LEARNLREFS of
Fig. 6 identifies any EFS
intime using
membership queries andsuperset queries, where.
$|\Sigma|\geq 5$

Conclusions

In this paper, we have investigated exact identification of an EFS in
using queries. We haveshown that any EFS in
is exactly identifiable intime using
membership
queries andsuperset queries, where. Moreover, we have shown that there exists nopolynomial time learning algorithm which identifies any EFS in $rSFS$ using membership, equivalence and subset queries. As future works, we willconsider the learnability ofin the frameworkof inductive inference from positive data.
$r\epsilon FS$$r\epsilon FS$$O(|\Gamma_{*}|^{4})$5$\tau$$\pi$

Hardness Results on Learnability

In this section, we show the insufficiency oflearning
in the query learning model. By
Lemma 3, we can show Theorem 4.
$t\epsilon \mathcal{F}S$

Lemma 3 [2] Suppose the hypothesis space contains a class of distinct sets
, and there
exists a set
which is not a hypothesis, suchthat for any pair of distinct indices and $j,$
. Then any algorithm that exactly identifies$O(|\Gamma_{*}|^{2})$$O(|\Gamma_{*}|^{2})$$|\Sigma|\geq$$5$$r\mathit{8}\mathcal{F}S$

References$L_{1,)}\ldots L_{N}$$L_{\cap}$$i$$L_{i}\cap L_{j}$$L_{\cap}=$[1] D. Angluin. Finding pattero common to aset of strings. Joumal of Computer and System Science, 21:46-62, 1980.

70
patterns with internal structured variablesfrom queries. Proc. AI-2002, Springer LNAI
2557, pages 523-534, 2002.

Algorithm LEARNLREFS
for the target
Given: An oracle
begin$\ell:=LENGTHl$ ;$\pi:=LEARNPI(\ell)$ ;if S up“yes“ then begin
if LEARNPI-TAUI $(\pi)=$ “no” then$S\mathrm{u}p_{\Gamma}$.

$\Gamma_{*};$[8] H. Sakamoto, K. Hirata, and H. Arimura.
Learning elementary formal systems with
queries.
Theoretical Computer Science,$\Gamma_{*}(\{\pi\})=$

298:21-50, 2003.

$H:=\{\pi\}$else begin
Let and be regular patterns
output by LEARNPI-TAUI$\pi’$$\tau’$$(\pi)$$\{\pi’’, \tau’’\}:=LEARNPI_{-}TAU\mathit{2}(\pi’, \tau’)$$H:=\{\pi’’, \tau’’\}$

;
;

;

end;
end else begin$w:=LENGTH\mathit{2}(\pi)$;

if $Sup_{\Gamma}.(\{\pi,\tau\})=$ “yes“ then
$H:=\{\pi, \tau\}$else begin$H:=(\pi, \tau’)$

233. Springer, 1998.

[10] T. Shinohara. Inductive inference of formal
systems from positive data. Bulletin of Informatics and Cybemetics, 22:9-18, 1986.

$\tau:=LEARN$-TA Ul $(\pi,$w);$\tau’:=LEARN_{-}TAU\mathit{2}(\pi,\tau)$[9] M. Sato, Y. Mukouchi, and D. Zheng. Characteristic sets for unions of regular patternlanguages and compactness. In Proc. ALT98, Springer- Verlag, LNAI 1501, pages220-

;

;

end;
end;
output H;
end.

Figure 6: Algorithm LEARNLREFS[2] D. Angluin. Queries and concept learning.
Machine Leaming, 2:319-342, 1988.

[3] S. Arikawa. Elementary formal systems andformal languages simple formal systems.
Memoirs of Faculty of Scien ce, Kyushu University, Series A, Mathematics, 24:47-75,
-

1970.

[4] S. Arikawa, T. Shinohara, and A. Yamamoto.
Learning elementary formal systems. Theoretical Computer Science, 95:97-113, 1992.
[5] S. Matsumoto and A. Shinohara. Learning pattern languages using queries. Proc.
EuroCOLT-97, Springer- Verlag, LNAI 1208,
pages 185-197, 1997.

[6] S. Matsumoto, A. Shinohara, H. Arimura,and T. Shinohara. Learning subsequence languages. In Information Modelling and Knowledge Bases VIlI, pages 335-344. IOS Press,

1997.

[7] S. Matsumoto, T. Shoudai, T. Miyahara, andT. Uchida. Learning of flnite unions of tree

[11] J. Uemura and M. Sato. Learning of erasing
primitive formal systems from positive examples. In Proc. ALT-2003, Springer- Verlag,

LNAI 2842, pages 69-83. Springer-Verlag,
2003.