Stochastic Finite Learning of Some Mildly
Context-Sensitive Languages
John Case1 , Ryo Yoshinaka2 , and Thomas Zeugmann3
1

Department of Computer and Information Sciences, University of Delaware
case@mail.eecis.udel.edu
2Graduate School of Informatics, Kyoto University
ry@i.kyoto-u.ac.jp
3
Division of Computer Science, Hokkaido University
thomas@ist.hokudai.ac.jp

Abstract. In recent years different classes of mildly context-sensitive
languages, which can handle complex structures beyond context-freeness,have been discovered that can be identified in the limit from positive
examples efficiently in some sense. The goal of this paper is to convert
those existing learning algorithms into ones that work under a morepractical learning scheme, finite stochastic learning and to discuss theefficiency of the proposed algorithms.

1

Introduction

Identification in the limit (iil) from text [8] is a classical paradigm that models language learning under an environment, where only positive examples areavailable. In fact in many real situations like when a child learns his/her first
language, negative examples are hardly available. After Angluin [1] showed thatpattern languages can be learned in this model, the literature has been paying
much attention to iil from text and obtained many fruitful results. However,this classical model is sometimes criticized for its inadequacy in practice. One
cannot know when the hypothesis output by the learner has converged. That is,
one cannot trust in the learner’s hypothesis regardless of the quantity of information fed to the learner. Moreover, it is hard to define the efficiency of a learningalgorithm due to the “in the limit” nature [4, 12]. We have no established way
to analyze the efficiency of an iil algorithm.
Reischuk and Zeugmann [13] and Rossmanith and Zeugmann [14] have proposed an alternative learning scheme, called stochastic finite ( sf) learning, toovercome those difficulties of iil. In their scheme, positive examples are sequentially given to a learner according to some probability distribution. Differently
from the iil model, an sf learner must eventually terminate and output a representation. One can evaluate a learner’s efficiency by, say the expected numberof examples that the learner needs to terminate. The literature has achieved
positive results on the sf learning [13, 14, 3, 18], yet so far the learning target
languages were limited to (variants of) pattern languages. This paper is concerned with the sf learning of the so-called mildly context-sensitive languages.

2

J. Case, R. Yoshinaka and T. Zeugmann

A long-term goal of grammatical inference is to find a reasonable class offormal languages that are powerful enough for expressing natural languages andare efficiently learnable under a reasonable scheme. Context-free languages are
fairly expressive, yet natural languages are known to involve non-context-freestructures like multiple agreements, crossed agreements, and duplication structures [9, 7, 15]. Joshi [10] proposed the notion of mildly context-sensitive languages in order to define a class of formal languages for modeling natural languages. They, on the one hand, should be rich enough to model the natural
language phenomena mentioned above. On the other hand, its generative powershould be still simple enough to allow for polynomial time parsing algorithms.
In recent years, several interesting iil algorithms for different mildly contextsensitive languages have been proposed. Among these algorithms are the one
discovered by Yoshinaka [16] that learns the class of qd-substitutable multiple
context-free languages, and Becerra-Bonache et al.’s [2] algorithms targeting simple external contextual languages.
In the present paper we shall focus on these algorithms and translate those
into sf learners. Section 3 shows how polynomial-time sf learning of qd-substitutable multiple context-free languages is possible under certain assumptions. We
also prove that a subclass of simple external contextual languages is sf learnable
in Section 4. In particular, it is shown that the class in concern is efficiently sf
learnable under a certain condition — whether or not the condition holds truein general is left as an open problem.

2

Preliminaries

For a finite alphabet Σ, let Σ ∗ denote the set of strings over Σ. The empty
string is denoted by λ and Σ + = Σ ∗ \ {λ}. For u ∈ Σ ∗ , let |u| denotes the lengthof u. Any subset L ⊆ Σ ∗ is called a language. For any set S, we use |S| to denoteits cardinality and ℘(S) to denote its power set. The empty set is P
denoted by ∅.
If L is a finite language over Σ, its size is defined as kLk = |L| + u∈L |u|.
We assume a countably infinite set Z of variables which is disjoint from Σ.
We use z1 , z2 , . . . , to denote variables. A pattern π is an element of (Z ∪ Σ)∗ .
A substitution is a homomorphism on (Z ∪ Σ)∗ that maps every letter in Σ
to itself. A homomorphism that maps zi to ui for i = 1, . . . , m is denoted asa suffix operator [z1 := u1 , . . . , zm := um ]. When z and u represent sequencesof variables z1 , . . . , zm and strings u1 , . . . , um , respectively, the substitution isoften denoted as [z := u].
Definition 1. A grammar system on Σ is a pair hG, Li where G is a class ofrepresentations called grammars and L is a function from G to ℘(Σ ∗ ) such that
it is decidable whether w ∈ L(G) for any G ∈ G and w ∈ Σ ∗ . We assume thatevery grammar G ∈ G is in some way assigned a positive integer called the sizeof G, denoted by kGk.
A probabilistic grammar system on Σ is a pair hH, Pr i where H is a class ofrepresentations and Pr is a function from H × (Σ ∗ ∪ {#}) to [0, 1] such that forStochastic Finite Learning of Some Mildly Context-Sensitive Languages

3

every H ∈ H, we haveX

Pr (H, w) = 1 ,w∈Σ ∗ ∪{#}

where # is a special symbol not in Σ. We call each element of H a probabilistic grammar. The function Pr H such that Pr H (w) = Pr (H, w) is called theprobabilistic language of H. We define the (non-probabilistic) language of H by
LPr (H) = { w ∈ Σ ∗ | Pr H (w) > 0 } .
We often describe a probabilistic grammar system H based on a grammar
system G, where each H is defined on G such that LPr (H) = L(G). Such G iscalled a underlying grammar of H and the size of each H is defined to be thatof G.
Definition 2. Let hH, Pr i be a probabilistic grammar system and hG, Li be
its underlying grammar system. A probabilistic text of H ∈ H is an infinite
sequence of elements of LPr (H) ∪ {#} independently drawn with respect to the
distribution Pr H . A stochastic finite learner (learner, in short) A is an algorithm
that takes strings from a probabilistic text of H one by one. Each time it getsa string, it may either request a next string or terminate outputting a grammar
G ∈ G. We say that a learner stochastically finitely ( sf) learns hH, Pr i if for any
H ∈ H, it terminates in a finite number of steps and the output G satisfies that
L(G) = LPr (H) with probability at least 1 − δ, where δ ∈ (0, 1) is the so-called
confidence parameter.
Moreover, we say that a learner polynomially stochastically finitely (psf)learns hH, Pr i if the expected number of examples that it requests is polynomially bounded in kHkδ −1 where H is the learning target and the total running
time is polynomially bounded in the total size of the given data.
We note that the above definition of sf learning differs from the original [13, 14]
slightly. Our definition of sf learning targets a probabilistic grammar system,
where we assume that a distribution of strings is in some way determined by partof a probabilistic grammar H. The original definition [13, 14] does not involveprobabilistic grammars, but still they assume that a probabilistic text obeys anadmissible distribution which may be defined in terms of underlying grammars.
When Pr is understood from the context, we let L denote LPr and simply
say that A (p)sf-learns H by dropping Pr .
Example 1. A pattern can be seen as a grammar, whose language is defined
to be the set of strings of letters that are obtained by substituting arbitrary
nonempty strings for variables. That is, L(π) = { πθ | θ is a λ-free substitution }.
For example, π = az1 bz2 z1 c is a pattern whose language is L(π) = { aubvuc |u, v ∈ Σ + }. Let D be a distribution of strings such that D(w) > 0 for all w ∈ Σ ∗and D(Σ ∗ ) = 1, which represents the probability of the substitution of a stringfor each variable that occursQin π. We extend the domain of D to tuples ofstrings by D(hu1 , . . . , uk i) = 1≤i≤k
P D(ui ). Then H = hπ, Di is a probabilistic
grammar such that P r(H, w) = u∈Sπ (w) D(u), where Sπ (w) = { hu1 , . . . , uk i |π[z1 := u1 , . . . , zk := uk ] = w } with the variables z1 , . . . , zk in π.

4

J. Case, R. Yoshinaka and T. Zeugmann

3

Learning multidimensionally substitutable MCFLs

3.1

Probabilistic multiple context-free grammars

A ranked alphabet is a pair of an alphabet V and a map r : Σ → N, whereN = {0, 1, 2, . . .} denotes the set of all natural numbers. Let x be any string
and m ∈ N, then xhmi denotes the m-tuple containing x precisely m manytimes, while xm denotes the usual concatenation of x, e.g., xh3i = hx, x, xi andx3 = xxx. Hence (Σ ∗ )hmi is the set of m-tuples of strings over Σ, which arecalled m-words. Similarly we define (·)h∗i and (·)h+i , where, for instance, (Σ ∗ )h+i
denotes the set of all m-words for all m ≥ 1. For an m-word u = hu1 , . . . , um i,we write
P |u| to denote its arity, i.e., |u| = m and we use kuk to denote its sizem + 1≤i≤m |ui |.
A multiple context-free grammar (mcfg) is a tuple G = hΣ, Ndim , R, Si,
where Σ is the alphabet of terminal symbols, Ndim = (N, dim) is the ranked
alphabet of nonterminal symbols, R is the finite set of rules and S ∈ N is thestart symbol. We call the value dim(A) the dimension of A ∈ N . Each rule in R
has the form
A0 (α1 , . . . , αr0 ) ← A1 (z1,1 , . . . , z1,r1 ), . . . , An (zn,1 , . . . , zn,rn )where Ai ∈ N and ri = dim(Ai ) for i = 0, 1, . . . , n, zi,j ∈ Z for i = 1, . . . , n
and j = 1, . . . , ri and αk ∈ (Σ ∪ { zi,j | 1 ≤ i ≤ n, 1 ≤ j ≤ ri })∗ for eachk = 1, . . . , r0 for some n ∈ N. Furthermore, in this paper we require each zi,jwith i = 1, . . . , n and j = 1, . . . , ri to occur exactly once through α1 , . . . , αr0 . A
rule of the above form is an A0 -rule and RA0 denotes the set of A0 -rules. The
size of the rule is defined to be |α1 | + · · · + |αr0 | + n + 1. The size of a grammar
is defined to be the sum of the sizes of its rules.
We represent ordered rooted labeled trees as terms. An A-derivation tree for
A ∈ N is a tree whose nodes are labeled by rules. We inductively define themas follows:– the tree consisting of just one node labeled by a rule of the formA(v1 , . . . , vr ) ← is an A-derivation tree;– if ti are Ai -derivation trees for all i = 1, . . . , n and a rule ρ has the formA(α) ← A1 (z 1 ), . . . , An (z n ), then ρ(t1 , . . . , tn ) is an A-derivation tree;– nothing else is an A-derivation tree.
A derivation tree means an S-derivation tree.
The yield YG (t) of an A-derivation tree t is a dim(A)-tuple of strings inductively defined by the following: If t = ρ(t1 , . . . , tn ) and ρ is a rule of the formA(α) ← A1 (z 1 ), . . . , An (z n ), thenYG (t) = α[z 1 := YG (t1 ), . . . , z n := YG (tn )] .
We set LG (A) = { YG (t) | t is an A-derivation tree }, and refer to it as thelanguage derived from a nonterminal A. The language of G is L(G) = LG (S).

Stochastic Finite Learning of Some Mildly Context-Sensitive Languages

5

A probabilistic mcfg is a tuple H = hΣ, N, R, S, πi, where GH = hΣ, N, R, Si
is an mcfg and π : R → (0, 1] gives a probability to each rule such thatX
π(ρ) = 1 , for all A ∈ N .
ρ∈RA

The mcfg GH is called the underlying grammar of H. The probability of an
A-derivation tree t is defined to be the product of the probabilities assigned torules that label nodes of t. That is, if t hasQthe form t = ρ(t1 , . . . , tn ), thenthe probability of t is defined by π̂(t) = π(ρ) 1≤i≤n π̂(ti ). The probability of astring u ∈ Σ ∗ assigned by a probabilistic grammar H is defined byX
π̂(t) ,
PrH (u) =t∈TS (u)where TA (u) is the set of A-derivation trees
P t such that YGH (t) = u. Moreover,
for a language K ⊆ Σ ∗ , we let PrH (K) = u∈K PrH (u). Obviously PrH (u) > 0
if and only if u ∈ L(GH ) for any u ∈ Σ ∗ . Note that we have π(ρ) > 0 for
all ρ ∈ R by definition.
Finally, we define PrH (#) = 1 − PrH (Σ ∗ ). Since H subsumes GH , we often
substitute H for G like YH or L(H) instead of YGH or L(GH ). The size kHk ofa probabilistic mcfg is defined to be the size of its underlying grammar.
3.2

IIL of multidimensionally substitutable MCFLs

Yoshinaka [16] has defined a subclass of mcfls that is interesting from its pointof view of learnability. Let  ∈/ Σ be a new symbol, which represents a hole.
If w ∈ (Σ ∪ {})∗ contains m occurrences of , then w is called an m-context.
For an m-context w = u0 u1  . . . um such that u0 , . . . , um ∈ Σ ∗ and an mword v = hv1 , . . . , vm i ∈ (Σ ∗ )h∗i , we define an operation by setting w v =u0 v1 u1 . . . vm um . Note that w v is defined only when w contains exactly |v|
occurrences of .
For a positive integer q, a language L is said to be qd-substitutable if andonly if
w1 v 1 , w1 v 2 , w2 v 1 ∈ L implies w2 v 2 ∈ L
for any w1 , w2 ∈ Σ ∗ (Σ + )m−1 Σ ∗ , v 1 , v 2 ∈ (Σ + )hmi and m ≤ q. For nota[m]tional convenience, we write Σ for Σ ∗ (Σ + )m−1 Σ ∗ .
We denote by G(q, r) the collection of mcfgs G whose nonterminals are assigned a dimension at most q and whose rules have at most r nonterminals on theright-hand side. Let SL(q, r) denote the set of languages that are qd-substitutable
and are generated by a grammar from G(q, r). The class SL(2, 1) contains noncontext-free languages like { an bcn den | n > 0 } and { am bcn dem f g n | m, n > 0 },which can be seen as models of multiple agreements and crossed agreements.
Yoshinaka’s [16] learning algorithm A(q, r) constructs a grammar GK froma finite set K of positive examples of the target language L ∈ SL(q, r) in thefollowing manner. The set of nonterminals is defined as
VK = { v ∈ (Σ + )hmi | w[m]v ∈ K for some w ∈ Σ and 1 ≤ m ≤ q } ∪ {S},6

J. Case, R. Yoshinaka and T. Zeugmann

where dim(v) = |v|. We shall write [[v]] instead of v for clarifying that it meansa nonterminal symbol (indexed with v). The set RK consists of rules of thefollowing three types:
I. [[v]](α) ←[[v 1 ]](z 1 ), . . . , [[v n ]](z n )if n ≤ r and v = α[z 1 := v 1 , . . . , z n := v n ], where [[v]], [[v 1 ]], . . . , [[v n ]] ∈VK − {S};[m]II. [[v]](z) ←[[v 0 ]](z) if there is a w ∈ Σ such that w v, w v 0 ∈ K;
III. S(z) ←[[hvi]](z) if v ∈ K.
Since the set VK is finite, the set RK is also finite. The conjecture made by thealgorithm A(q, r) is then the mcfg Gq,r (K) = hΣ, VK , RK , Si ∈ G(q, r).
It is shown in [16] that for any qd-substitutable language L∗ and any K ⊆ L∗ ,we have L(Gq,r (K)) ⊆ L∗ . Furthermore, there exists also a set KG∗ such thatL∗ = L(Gq,r (K)) for any K ⊇ KG∗ , where G∗ is a grammar generating L∗ .
Proposition 1 (Yoshinaka [16]). One can compute Gq,r (K) from a finite
language K ⊂ Σ ∗ in polynomial time. Assume that K ⊇ KG∗ for an mcfg
G∗ ∈ G(q, r). Then we have L(G∗ ) ⊆ Gq,r (KG∗ ). In particular, if L(G∗ ) is qdsubstitutable, then L(Gq,r (K)) = L(G∗ ).
3.3

Polynomial stochastic finite learning of substitutable MCFLs

Based on Yoshinaka’s [16] iil algorithm, we shall investigate (p)sf-learning of
qd-substitutable mcfgs. Our learner outputs the grammar Gq,r (K) from a given
positive data set K when a sufficient number of examples is received. Let G =hΣ, N, R, S, πi be a probabilistic mcfg of our learning target. This paper gives adefinition of KG in a way different from the original one, but still Proposition 1
holds with our definition. For each rule ρ ∈ R, among derivation trees that havea node labeled with ρ, let tρ be the one with the largest probability. We thendefine KG = { vρ | ρ ∈ R } where vρ = YG (tρ ). We estimate PrG (vρ ) for eachρ ∈ R in order to determine how many examples our learner should request.
For each nonterminal A ∈ N , the most probable A-derivation tree has at
most (r|V | − 1)/(r − 1) nodes where r is the maximum number of nonterminals
that appear on the right-hand side of a rule. Obviously every subtree of tρ is themost probable A-derivation tree except the ones rooted by nodes on the pathfrom the root to a node labeled by ρ, whose length is at most |V |. Every nodeon the path has at most r − 1 siblings and the node labeled with ρ has at most r
children, all of which are a root node of the most probable A-derivation tree forsome A ∈ N . Therefore, we have|tρ | ≤ |V | − 1 + ((r − 1)|V | + 1)(r|V | − 1)/(r − 1) ≤ (|V | + 1)r|V |and hence
PrG (vρ ) ≥ π̂(tρ ) ≥ p(|V |+1)r

|V |

,
|V |

where p is the least probability assigned to a rule in R. Let s = p(|V |+1)r . LetZρm denote the event that one does not observe vρ among randomly drawn m

Stochastic Finite Learning of Some Mildly Context-Sensitive Languages

7

examples. We have P(Zρm ) ≤ (1 − s)m ≤ e−ms and thus the probability that wemiss vρ for some ρ ∈ R can be bounded as follows
[
 X
P
Zρm ≤
P(Zρm ) ≤ |R|e−ms ,
ρ∈R

ρ∈R

where e is Napier’s constant. Thus if we draw more than s−1 ln |R|δ −1 examples,with probability at least 1 − δ we obtain vρ for all ρ ∈ R.
This number of required examples is not polynomially bounded in the de|V |scription size of the target grammar because of s = p(|V |+1)r . That is, eventhe most probable derivation tree of a grammar appear exponentially rarely.
This is closely related to the well-known problem in the efficient learning of
cfgs and richer formalisms: even the simplest derivation trees of a grammar
may be exponentially large in the size of the grammar itself. Here we assume
the µ-observability saying that we have a reasonably enough chance µ to observe the most probable string vρ for each ρ: PrG (vρ ) ≥ µ. This can be seen
as an analogous property to the µ1 -distinguishability and µ2 -reachability that
Clark [5] has assumed to achieve a pac-type learnability of a subclass of cfgs.
The µ1 -distinguishability and µ2 -reachability entails that every nonterminal A
has a string vA derived by using A whose probability is at least µ1 µ2 . We assume
the similar property for each rule. If a rule is hardly used, we have little chance
to learn it. Moreover, this assumption entails that |R| is also bounded by µ−1 .
Hence, if we draw more than
1
1
ln
µ µδ
examples, our grammar constructed on those examples generates the target language exactly with probability at least 1 − δ.
Theorem 1. Let G(q, r, µ) be the class of probabilistic mcfgs in G(q, r) whose
languages are qd-substitutable and µ-observable. The class G(q, r, µ) is psflearnable.
We remark that the above discussion on the psf-learning of qd-substitutablemcfgs apply to other formalisms for which substitutability is accordingly definedand shown to be learnable: like cfgs [6], simple context-free tree grammars [11]and abstract categorial grammars [17].

4Stochastic finite learning of simple external contextual
grammars with one context

Becerra-Bonache et al. [2] have discussed the learnability of subclasses of simple
external contextual grammars ( secgs). A (q, s)-secg is a pair G = (v, C) where|v| = q, |C| ≤ s and C ⊆ (Σ ∗ Σ ∗ )hqi . We call v and elements of C the baseand contexts of G, respectively. The language of G, which we call a (q, s)-secl,
is given by
L(G) = { q

w1

···

wn

v | w1 , . . . , wn ∈ C }8

J. Case, R. Yoshinaka and T. Zeugmann(note that is associative). An secg can be seen as a special case of an mcfg.
Becerra-Bonache et al. [2] give an iterative learning algorithm for (q, 1)-secgs.
This section translates their algorithm into an sf learner. Following them, forease of notation, when we say that a language equals {u0 , u1 , . . . }4 , we assume
that the ui are listed in length increasing order, that is, |u0 | < |u1 | < |u2 | < . . . .
For a (q, 1)-sec language {u0 , u1 , . . . }, it would be a natural idea to define aprobabilistic distribution of strings by Pr (ui ) = pi (1 − p) where 0 < p < 1.
The following theorem is a key ingredient that establishes the result obtainedby Becerra-Bonache et al. [2].
Theorem 2 (Becerra-Bonache et al. [2], Theorem 22).
Let V = {v0 , v1 , v2 , . . . } and W = {w0 , w1 , w2 , . . . } be (q, 1)-secls. If v0 = w0 ,v1 = w1 and there are m, n with vn = wm ∧ |vn | > (|v1 | + 2)3 then V = W .
It is easily seen that there is a polynomial-time algorithm (q is fixed) thatfor input strings u0 , u1 , u with |u0 | < |u1 | < |u| decides whether there is an(q, 1)-secl {u0 , u1 , . . . , u, . . . , }, and moreover if it is the case it outputs a (q, 1)secg Hq (u0 , u1 , u) generating the language. If there is no such a grammar thenHq (u0 , u1 , u) is undefined.
Therefore what is important is to identify the two shortest strings in thelearning target. Our sf learner assumes that the two shortest strings u0 , u1
amongst examples are indeed the two shortest in the target language when bothstrings have been drawn at least n times where n is determined by the confidence
parameter δ. When in addition it observes a string u such that |u| > (|u1 | + 2)3 ,it outputs Hq (u0 , u1 , u) as its conjecture.
Suppose that the target language is L∗ = {v0 , v1 , . . . , }. We bound the probability that the output of our learner is wrong, which happen only when u0
is not the shortest or u1 is not the second shortest in L∗ . Let Zj denote theevent that vj is drawn n times before none of vi with i < j is drawn. Notethat Pr (vj+1 ) ≤ Pr (vj ) for all j ≥ 0. Hence Pr(Zj ) < (j + 1)−n . Thus, theprobability that u0 is not the shortest is bounded from above by
Z ∞
[
X
1
1
3
1
<
+
dx < nPr(Zj ) <n
(j + 1)n
2n
x
2
2
j≥1

j≥1

for n ≥ 2. The probability that u1 is not the second shortest is similarly bounded
3
from above by 23n . Therefore, the failure probability is at most 2n−1
, which should
3
be bounded by 1 − δ. In other words, for n ≥ 1 + log2 δ , our learner’s conjectureis exactly correct with probability at least 1 − δ.
Theorem 3. The class of (q, 1)-secgs is sf learnable.
Note that this theorem holds true as long as Pr(vi ) ≥ Pr(vj ) whenever i ≤ j.
Next we estimate the expected number of examples that the learner requests.
As in the previous section, we assume that the probabilities (p and 1−p) assigned
4

We assume that every (q, 1)-secg in this paper generates an infinite language; otherwise, its language is only a singleton.

Stochastic Finite Learning of Some Mildly Context-Sensitive Languages

9

to rules are bounded from below by a constant. The probability that we draw
vj for some j ≥ k is pk . Taking into account that |vk | = |v0 | + k(|v1 | − |v0 |), fork > ((|v1 | + 2)3 − |v0 |)/(|v1 | − |v0 |), we have |vk | > (|v1 | + 2)3 . Thus the numberof expected times that we draw positive examples until we find a long enoughone is at most p−k where k = d((|v1 | + 2)3 − |v0 |)/(|v1 | − |v0 |)e + 1, which is
not polynomially bounded by the size of the target grammar if we define thesize of an secg G = hv, Ci to be kCk + kvk, which is equivalent to |w1 | modulo
a constant term. On the other hand, it is open whether one can strengthen
Theorem 2 so that w0 , w1 , wn with n ≥ 2 suffices for ensuring the uniqueness.
If one can answer the open problem in the affirmative, it is not hard to see thatthe class of (q, 1)-secgs becomes psf-learnable.
At least it is the case when q = 1, where (q, 1)-secgs generate only linear
context-free languages.
Lemma 1. Let Pk be the equation uk vwk = (u0 )k v(w0 )k . P1 ∧ P2 implies ∀k.Pk .
Corollary 1. The class of (1, 1)-secgs is psf-learnable under the assumptionthat the probability of drawing each of the shortest three positive example isbounded from below.

5

Discussion

While language classes targeted by finite stochastic learning have so far been
limited to pattern languages in the literature, this paper has discussed how existing learning algorithms for mildly context-sensitive languages working under
the identification in the limit paradigm can be translated into finite stochastic
learners. The positive result on qd-substitutable substitutable mcfls can easily be applied to the “substitutable” subclasses of other formalisms including
context-free string/tree languages [6, 11] and abstract categorial grammars [17]as well.
On the other hand, while we have established a positive result on the sf
learning of (q, 1)-secgs, it remains open whether (q, 1)-secls are psf learnable
for q ≥ 2. At last, we remark another open problem related to the learningalgorithm for (q, r)-secls from Becerra-Bonache et al.’s paper [2, Theorem 8].
Translating their algorithm into one for sf learning does not seem easy, since
their learnability proof does not constructively describe a set of positive examples
on which their learner converges to a correct grammar for the learning target.

Acknowledgement
The authors would like to thank Chihiro Shibata for a useful suggestion on partof our technical discussions.

10

J. Case, R. Yoshinaka and T. Zeugmann

References[1] D. Angluin. Finding patterns common to a set of strings. J. of Comput. Syst.
Sci., 21(1):46–62, 1980.
[2] L. Becerra-Bonache, J. Case, S. Jain, and F. Stephan. Iterative learning of simple
external contextual languages. Theoret. Comput. Sci., 411:2741–2756, 2010.
[3] J. Case, S. Jain, R. Reischuk, F. Stephan, and T. Zeugmann. Learning a subclassof regular patterns in polynomial time. Theoret. Comput. Sci., 364:115–131, 2006.
Special Issue for ALT’03.
[4] J. Case and T. Kötzing. Difficulties in forcing fairness of polynomial time inductive inference. In R. Gavaldà, G. Lugosi, T. Zeugmann, and S. Zilles, editors,
Algorithmic Learning Theory, 20th International Conference, ALT 2009, Porto,
Portugal, October 2009, Proceedings, volume 5809 of Lecture Notes in Artificial
Intelligence, pages 263–277, Berlin/Heidelberg, 2009. Springer.
[5] A. Clark. PAC-learning unambiguous NTS languages. In Grammatical Inference:
Algorithms and Applications, 8th International Colloquium, ICGI 2006, Tokyo,
Japan, September 20-22, 2006, Proceedings, volume 4201 of Lecture Notes in Artificial Intelligence, pages 59–71, Berlin, 2006. Springer.
[6] A. Clark and R. Eyraud. Polynomial identification in the limit of substitutable
context-free languages. Journal of Machine Learning Research, 8:1725–1745, 2007.
[7] C. Culy. The complexity of the vocabulary of Bambara. Linguistics and Philosophy, 8:345–351, 1985.
[8] E. M. Gold. Language identification in the limit. Inform. Control, 10(5):447–474,
1967.
[9] S. P. Joan Bresnan, Ronald M. Kaplan and A. Zaenen. Cross-serial dependencies
in dutch. Linguistic Inquiry, 13:613–635, 1982.
[10] A. K. Joshi. Tree adjoining grammars: how much context-sensitivity is required
to provide reasonable structural descriptions? In D. R. Dowty, L. Karttunen,and A. Zwicky, editors, Natural Language Parsing, pages 206–250. Cambridge
University Press, Cambridge, MA, 1985.
[11] A. Kasprzik and R. Yoshinaka. Distributional learning of simple context-free treegrammars. In J. Kivinen, C. Szepesvári, E. Ukkonen, and T. Zeugmann, editors,
ALT, volume 6925 of Lecture Notes in Computer Science, pages 398–412. Springer,
2011.
[12] L. Pitt. Inductive inference, DFAs, and computational complexity. In Analogical and Inductive Inference, Proceedings of the Second International Workshop(AII’89), volume 397 of Lecture Notes in Artificial Intelligence, pages 18–44.
Springer-Verlag, Berlin, 1989.
[13] R. Reischuk and T. Zeugmann. An average-case optimal one-variable patternlanguage learner. J. Comput. Syst. Sci., 60(2):302–335, 2000.
[14] P. Rossmanith and T. Zeugmann. Stochastic finite learning of the pattern languages. Machine Learning, 44(1/2):67–91, 2001.
[15] S. Shieber. Evidence against the context-freeness of natural language. Linguistics
and Philosophy, 8:333–343, 1985.
[16] R. Yoshinaka. Learning multiple context-free languages with multidimensional
substitutability from positive data. Inform. Comput., 412:1821–1831, 2011.
[17] R. Yoshinaka and M. Kanazawa. Distributional learning of abstract categorial
grammars. In S. Pogodalla and J.-P. Prost, editors, LACL, volume 6736 of Lecture
Notes in Computer Science, pages 251–266. Springer, 2011.
[18] T. Zeugmann. From learning in the limit to stochastic finite learning. Theoret.
Comput. Sci., 364(1):77–97, 2006.