Alexander Clark

Rémi Eyraud
email: remi.eyraud@lif.univ-mrs.fr

Amaury Habrard
email: amaury.habrard@lif.univ-mrs.fr

Using Contextual Representations to Efficiently Learn Context-Free Languages

Keywords: grammatical inference, context-free language, positive data only, membership queries

We present a polynomial update time algorithm for the inductive inference of a large class of context-free languages using the paradigm of positive data and a membership oracle. We achieve this result by moving to a novel representation, called Contextual Binary Feature Grammars (CBFGs), which are capable of representing richly structured contextfree languages as well as some context sensitive languages. These representations explicitly model the lattice structure of the distribution of a set of substrings and can be inferred using a generalisation of distributional learning. This formalism is an attempt to bridge the gap between simple learnable classes and the sorts of highly expressive representations necessary for linguistic representation: it allows the learnability of a large class of contextfree languages, that includes all regular languages and those context-free languages that satisfy two simple constraints. The formalism and the algorithm seem well suited to natural language and in particular to the modeling of first language acquisition. Preliminary experimental results confirm the effectiveness of this approach.

Introduction

In natural language processing, many applications require the learning of powerful grammatical models. One of the central concerns of generative linguistics is the definition of an adequate formalism that needs to satisfy two different objectives. On the one hand, such a formalism must be expressive enough to describe natural languages. On the other hand, it has to be sufficiently constrained to be learnable from the sort of linguistic data available to the child learner [START_REF] Chomsky | Knowledge of Language : Its Nature, Origin, and Use[END_REF]. In this context, there are two possible research strategies. One is to take a descriptively adequate formalism such as Tree Adjoining Grammars [START_REF] Joshi | Tree-adjoining grammars[END_REF] or some other mildly context sensitive grammatical c 2010 Alexander Clark, Rémi Eyraud and Amaury Habrard.

formalism and try to construct learning algorithms for that class. However, such a strategy is unlikely to be successful because classes that are so powerful are difficult to handle from a machine learning point of view. The other approach, which we adopt in this paper, consists in switching to a formalism that is in some sense intrinsically learnable, and seeing whether we can represent linguistically interesting formal languages in that representation.

Grammatical inference is the machine learning domain which aims at studying learnability of formal languages. While many learnability results have been obtained for regular languages [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF][START_REF] Carrasco | Learning stochastic regular grammars by means of a state merging method[END_REF], this class is not sufficient to correctly represent natural languages. The next class of languages to consider is the class of context-free languages (CFL). Unfortunately, there exists no learnability results for the whole class. This may be explained by the fact that this class relies on syntactic properties instead of intrinsic properties of the language like the notion of residuals for regular languages [START_REF] Denis | Learning regular languages using rfsas[END_REF]. Thus, most of the approaches proposed in the literature are either based on heuristics [START_REF] Nakamura | Incremental learning of context-free grammars based on bottom-up parsing and search[END_REF][START_REF] Langley | Learning context-free grammars with a simplicity bias[END_REF] or are theoretically well founded but concern very restricted subclasses of context-free languages [START_REF] Eyraud | Lars: A learning algorithm for rewriting systems[END_REF][START_REF] Yokomori | Polynomial-time identification of very simple grammars from positive data[END_REF][START_REF] De | Inferring deterministic linear languages[END_REF]. Some of these approaches are built from the idea of distributional learning1 , normally attributed to [START_REF] Harris | Distributional structure[END_REF]. The basic principle -as we reinterpret it in our work -is to look at the set of contexts that a substring can occur in. The distribution of a substring is the linguistic way of referring to this set of contexts. This idea has formed the basis of many heuristic algorithms for learning context-free grammars (see [START_REF] Adriaans | Learning shallow context-free languages under simple distributions[END_REF] for instance). However, a recent approach by [START_REF] Clark | Polynomial identification in the limit of substitutable context-free languages[END_REF], has presented an accurate formalisation of distributional learning. From this formulation, a provably correct algorithm for contextfree grammatical inference was given in the identification in the limit framework, albeit for a very limited subclass of languages, the substitutable languages. From a more general point of view, the central insight is that it is not necessary to find the non-terminals of the context-free grammar (CFG): it is enough to be able to represent the congruence classes of a sufficiently large set of substrings of the language and to be able to compute how they combine. This result was extended to a PAC-learning result under a number of different assumptions [START_REF] Clark | PAC-learning unambiguous NTS languages[END_REF] for a larger class of languages, and also to a family of classes of learnable languages [START_REF] Yoshinaka | Identification in the limit of k,l-substitutable context-free languages[END_REF].

Despite their theoretical bases, these results are still too limited to form the basis for models for natural language. There are two significant limitations to this work: first it uses a very crude measure for determining the syntactic congruence, and secondly the number of congruence classes required will in real cases be prohibitively large. If each non-terminal corresponds to a single congruence class (the NTS languages [START_REF] Boasson | NTS languages are deterministic and congruential[END_REF]), then the problem may be tractable. However in general the contexts of different non-terminals overlap enormously: for instance the contexts of adjective phrases and noun phrases in English both contain contexts of the form ("it is", "."). Problems of lexical ambiguity also cause trouble. Thus for a CFG it may be the case that the number of congruence classes corresponding to each non-terminal may be exponentially large (in the size of the grammar). But the situation in natural language is even worse: the CFG itself may have an exponentially large number of non-terminals to start off with! Conventional CFGs are simply not sufficiently expressive to be cognitively plausible representations of natural language: to write a CFG requires a multiplication of the numbers of non-terminals to handle phenomena like subject verb agreement, gender features, displaced constituents, etc. This requires the use of a formalism like GPSG (Generalised Phrase Structure Grammar) [START_REF] Gazdar | Generalised Phrase Structure Grammar[END_REF] to write a meta-grammar -a compact way of specifying a very large CFG with richly structured non-terminals. Thus we cannot hope to learn natural languages by learning one congruence class at a time: it is vital to use a more structured representation.

This is the objective of the approach introduced in this article: for the first time, we can bridge the gap between theoretically well founded grammatical inference methods and the sorts of structured representations required for modeling natural languages.

In this paper, we present a family of representations for highly structured context-free languages and show how they can be learned. This is a paper in learning, but superficially it may appear to be a paper about grammatical representations: much of the work is done by switching to a more tractable formalism, a move which is familiar to many in machine learning. From a machine learning point of view, it is a commonplace that switching to a better representation -for example, through a non-linear map into some feature spacemay make a hard problem very easy.

The contributions of this paper are as follows: we present in Section 3 a rich grammatical formalism, which we call Contextual Binary Feature Grammars (CBFG). This grammar formalism is defined using a set of contexts which play the role of features with a strict semantics attached to these features. Though not completely original, since it is closely related to a number of other formalisms such as Range Concatenation Grammars [START_REF] Boullier | A Cubic Time Extension of Context-Free Grammars[END_REF], it is of independent interest. We consider then the case when the contextual features assigned to a string correspond to the contexts that the string can occur in, in the language defined by the grammar. When this property holds, we call it an exact CBFG. The crucial point here is that for languages that can be defined by an exact CBFG, the underlying structure of the representation relies on intrinsic properties of the language easily observable on samples by looking at context sets.

The learning algorithm is defined in Section 4. We provide some conditions, both on the context sets and the learning set, to ensure the learnability of languages that can be represented by CBFG. We prove that this algorithm can identify in the limit this restricted class of CBFGs from positive data and a membership oracle.

Some experiments are provided in Section 5: these experiments are intended to demonstrate that even quite naive algorithms based on this are efficient and effective at learning context-free languages.

Section 6 contains a theoretical study on the expressiveness of CBFG representations. We investigate the links with the classical Chomsky hierarchy, some well known grammatical representations used in natural language processing. An important result about the expressive power of the class of CBFG is obtained: it contains all the context-free languages and some non context-free languages. This makes this representation a good candidate for representing natural languages. However exact CBFG do not include all context-free languages but do include some non context-free ones, thus they are orthogonal with the classic Chomsky hierarchy and can represent a large class of languages. This expressiveness is strengthened by the fact that exact CBFG contains most of the existing learnable classes of languages.

Basic Definitions and Notations

We begin by some standard notations and definitions used all along the paper.

We consider a finite alphabet Σ as a finite non-empty set of symbols also called letters. A string (also called word) u over Σ is a finite sequence of letters u = u 1 • • • u n . Let |u| denote the length of u. The set of all strings over Σ is denoted by Σ * , corresponding to the free monoid generated by Σ. λ denotes the empty string and Σ + = Σ * \{λ}. A language L is any subset L ⊆ Σ * .

We will write the concatenation of u and v as uv, and similarly for sets of strings. u ∈ Σ * is a substring of v ∈ Σ * if there are strings l, r ∈ Σ * such that v = lur. Define Sub(u) to be the set of non-empty substrings of u. For a set of strings S define Sub(S) = u∈S Sub(u).

A context is an element of Σ * × Σ * . For a string u and a context f = (l, r) we write f ⊙ u = lur; the insertion or wrapping operation. We extend this to sets of strings and contexts in the natural way. We define by Con(w) = {(l, r)|∃u ∈ Σ + : lur = w} i.e. the set of all contexts of a word w. Similarly, for a set of strings, we define: Con(S) = w∈S Con(w).

We give now a formal definition of the set of contexts since it represents a notion often used in the paper.

Definition 1 The set of contexts, or context distribution, of a string u in a language L is, C L (u) = {(l, r) ∈ Σ * × Σ * |lur ∈ L}. We will often drop the subscript where there is no ambiguity.

Definition 2 Two strings u and v are syntactically congruent with respect to a language L, denoted u ≡ L v, if and only if

C L (u) = C L (v).
The equivalence classes under this relation are the congruence classes of the language.

After these basic definitions and notations, we recall here the definition of a context-free grammar which is a class which is close to the language class studied in this paper.

Definition 3 A context-free grammar (CFG) is a quadruple G = (Σ, V, P, S). Σ is a finite alphabet of terminal symbols, V is a set of non terminals s.t. Σ ∩ V = ∅, P ⊆ V × (V ∪ Σ) + is a finite set of productions, S ∈ V is the start symbol.
We denote a production of P : N → α with N ∈ V and α ∈ (V ∪ Σ) + . We will write

uN v ⇒ G uαv if there is a production N → α in G. * ⇒ G denotes the reflexive transitive closure of ⇒ G .
The language defined by a CFG G is

L(G) = {w ∈ Σ * |S

Contextual Binary Feature Grammars (CBFG)

Distributional learning, in our view, involves explicitly modeling the distribution of the substrings of the language -we would like to model C L (w). Clearly a crucial element of this distribution is the empty context (λ, λ): (λ, λ) ∈ C L (w) if and only if w ∈ L. Our goal is to construct a representation that allows us to recursively compute a representation of the distribution of a string w, C L (w), from the (representations of) the distributions of its substrings.

The representation by contextual binary feature grammars relies on the inclusion relation between sets of contexts of language L. In order to introduce this formalism, we propose, for a start, to present some preliminary results on context inclusion. These results will lead us to define a relevant representation for modeling these inclusion dependencies by the notion of contextual binary feature grammars.

Preliminary Results about Context Inclusion

The objective of this section is to give some information about contexts that will help to give an intuition about the representation. The basic insight behind CBFGs is that there is a relation between the contexts of a string w and the contexts of its substrings. This is given by the following trivial lemma: Lemma 4 For any language L and for any strings

u, u ′ , v, v ′ if C(u) = C(u ′ ) and C(v) = C(v ′ ), then C(uv) = C(u ′ v ′ ).
Proof We write out the proof completely as the ideas will be used later on. Suppose we have u, v, u ′ , v ′ that satisfy the conditions. If (l, r) ∈ C(uv), then (l, vr) ∈ C(u) and thus (l, vr) ∈ C(u ′ ). As a consequence, (lu ′ , r) ∈ C(v) and then (lu ′ , r) ∈ C(v ′ ) which implies that (l, r) ∈ C(u ′ v ′ ). Symmetrically, by using the same arguments, we can show that (l, r)

∈ C(u ′ v ′ ) implies (l, r) in C(uv). Thus C(uv) = C(u ′ v ′ ).
This establishes that the syntactic monoid Σ * / ≡ L is well-defined; from a learnability point of view this means that if we want to compute the contexts of a string w we can look for a split into two strings uv where u is congruent to u ′ and v is congruent to v ′ ; if we can do this and we know how u ′ and v ′ combine, then we know that the contexts of uv will be exactly the contexts of u ′ v ′ . There is also a slightly stronger result:

Lemma 5 For any language L and for any strings

u, u ′ , v, v ′ if C(u) ⊆ C(u ′ ) and C(v) ⊆ C(v ′ ), then C(uv) ⊆ C(u ′ v ′ ).
Proof See proof of Lemma 4. C(u) ⊆ C(u ′ ) means that we can replace any occurrence in a sentence of u with a u ′ , without affecting the grammaticality, but not necessarily vice versa. Note that none of these strings need to correspond to non-terminals: this is valid for any fragment of a sentence.

We will give a simplified example from English syntax: the pronoun "it" can occur everywhere that the pronoun "him" can, but not vice versa2 . Thus given a sentence "I gave him away", we can substitute "him" for "it", to get the grammatical sentence "I gave it away", but we cannot reverse the process. For example, given the sentence "it is raining", we cannot substitute "him" for "it", as we will get the ungrammatical sentence "him is raining". Thus we observe C(him) C(it).

Looking at Lemma 5 we can also say that, if we have some finite set of strings K, where we know the contexts, then:

Corollary 6 For any language L and for any set of strings K, we have:

C(w) ⊇ u ′ ,v ′ : u ′ v ′ =w u∈K: C(u)⊆C(u ′ ) v∈K: C(v)⊆C(v ′ ) C(uv).
This is the basis of our representation: a word w is characterised by its set of contexts. We can compute the representation of w, from the representation of its parts u ′ , v ′ , by looking at all of the other matching strings u and v where we understand how they combine (with subset inclusion). Rather than representing just the congruence classes, we will represent the lattice structure of the set of contexts using subset inclusion; sometimes called Dobrušin-domination [START_REF] Marcus | Algebraic Linguistics; Analytical Models[END_REF].

The key relationships are given by context set inclusion. Contextual binary feature grammars allow a proper definition of the combination of context inclusion.

Contextual Binary Feature Grammars

The formalism of contextual binary feature grammars has some resemblance with Generalized Phrase Structure Grammar (GPSG) [START_REF] Gazdar | Generalised Phrase Structure Grammar[END_REF], and most importantly the class of Range Concatenation Grammars (RCG) [START_REF] Boullier | A Cubic Time Extension of Context-Free Grammars[END_REF]; these relationships will be detailed in Section 6. As we will see later, note that our formalism defines a class orthogonal to the class of context-free grammars, indeed the use of subsets inclusion allows to model non context-free languages (although not all the context-free languages can be represented).

Definition 7 A Contextual Binary Feature Grammar (CBFG) G is a tuple F, P, P L , Σ :

• F is a finite set of contexts, (i.e. F ⊂ Σ * ×Σ * ) called features, where we write E = 2 F for the power set of F defining the categories of the grammar, and where (λ, λ) ∈ F .

• P ⊆ E × E × E is a finite set of productions that we write x → yz where x, y, z ∈ E,

• P L ⊆ E × Σ is a set of lexical rules, written x → a,
• Σ denotes the alphabet.

Given a CBFG G we can recursively define a function f G from Σ * → E as follows:

f G (λ) = ∅ (1) f G (w) = (c→w)∈P L c iff |w| = 1 (2) f G (w) = u,v:uv=w x→yz∈P : y⊆f G (u)∧ z⊆f G (v) x iff |w| > 1. ( 3
)
Given a CBFG G and a string w it is possible to compute f G (w) in time O(|F ||P ||w| 3 ) using standard dynamic programming techniques. A straightforward modification of the Cocke-Kasami-Younger algorithm for parsing Context-Free Grammars will suffice.

Thus a CBFG, G, defines for every string u a set of contexts f G (u): this will be a representation of the context distribution. f G (u) will be a subset of F : we will want f G (u) to approximate C L (u) ∩ F . The natural way to define the membership of a string w in L(G) is to have the context (λ, λ) ∈ f G (w).

Definition 8 The language defined by a CBFG G is the set of all strings that are assigned the empty context:

L(G) = {u|(λ, λ) ∈ f G (u)}.
We give here more explanation about the function f G . A rule x → yz is applied to analyse a string w if there is a split or cut of the string w into two strings u and v such that uv = w s.t. y ⊆ f G (u) and z ⊆ f G (v) -recall that y and z are sets of features.

One way of viewing a production x → yz is as an implication: if two strings u and v are such that they have the features y and z, then their concatenation will have the features x. As features correspond to contexts, intuitively, the relation given by the production rule is linked with Lemma 5: x is included in the set of features of w = uv. From this relationship, for any (l, r) ∈ x we have lwr ∈ L(G).

The complete computation of f G is then justified by Corollary 6: f G (w) defines all the possible contextual features associated by G to w with all the possible cuts uv = w (i.e. all the possible derivations).

Note the relation between the third clause above and Corollary 6. In general we will apply more than one production at each step of the analysis.

We will discuss the relation between this class and the class of CFGs in some detail in Section 6. For the moment, we will just make the following points. First, the representation is quite close to that of a CFG where the non-terminals correspond to sets of contexts (subsets of F ). There are, however, crucial differences: the very fact that they are represented by sets means that the non-terminals are no longer atomic symbols but rather structures; the formalism can combine different rules together at each step. Secondly, the function f G can aggregate different trees together. It is not the case that every feature assigned to w must come from the same split of w into u and v. Rather some features could come from one split, and some from another: these two sets of features can be combined in a single derivation even though they come from different trees. It is this property that takes the class of languages out of the class of context-free languages. In the special case where all of the productions involve only singleton sets then this will reduce to a CFG -the non-terminals will correspond to the individual features, and f G (w) will correspond to the set of non-terminals that can derive the string w.

Clearly by the definition of L(G) we are forcing a correspondence between the occurrence of the context (λ, λ) in C L (w) and the occurrence of the feature (λ, λ) in f G (w). But ideally we can also require that f G defines exactly the possible features that can be associated to a given string according to the underlying language. Indeed, we are interested in cases where there is a correspondence between the language theoretic interpretation of a context, and the occurrence of that context as a feature in the grammar: in this case the features will be observable which will lead to learnability. This is formalised via the following definitions.

Definition 9 Given a finite set of contexts F = {(l 1 , r 1 ), . . . , (l n , r n )} and a language L we can define the context feature function

F L : Σ * → 2 F which is just the function u → {(l, r) ∈ F |lur ∈ L} = C L (u) ∩ F .
Using this definition, we now need a correspondence between the language theoretic context feature function F L and the representation in our CBFG, f G .

Definition 10 A CBFG G is exact if for all u ∈ Σ * , f G (u) = F L(G) (u).
Example. Let L = {a n b n |n > 0}. Let F, (λ, λ), P, P L , Σ a CBFG s.t. F = {(λ, λ), (a, λ), (aab, λ), (λ, b), (λ, abb)}. The lexical productions in P L are: {(λ, b), (λ, abb)} → a and {(a, λ), (aab, λ)} → b. Note that these lexical productions are of the form x → a, where x is a subset of F , that is to say, a set of features. The rule {(λ, b), (λ, abb)} → a therefore says that the letter a will be assigned both of the features/contexts (λ, b) and (λ, abb). Since this is the only lexical rule for a, we will have that f G (a) = {(λ, b), (λ, abb)}. The productions in P , denoted by x → yz, where x, y, z are again sets of contexts, are defined as:

{(λ, λ)} → {(λ, b)}{(aab, λ)}, {(λ, λ)} → {(λ, abb)}{(a, λ)}, {(λ, b)} → {(λ, abb)}{(λ, λ)}, {(a, λ)} → {(λ, λ)}{(aab, λ)}.
In each of these rules, in this trivial case, the sets of contexts are singleton sets. In general, these productions may involve sets that have more than one element. This defines an exact CBFG for L. Indeed, the grammar assigns only (λ, λ) to the elements of the language; for all elements w of {a n b n+1 : n > 1} we have f G (w) = {(a, λ)} = F L (w) and for all all elements w of {a n+1 b n : n > 1}, f G (w) = {(λ, b)} = F L (w); The lexical rules assign correct contexts to each letter.

Exact CBFGs are a more limited formalism than CBFGs themselves; without any limits on the interpretation of the features, we can define a class of formalisms that is equal to the class of Conjunctive Grammars (see Section 6.2.3). However, exactness is an important property because it allows to associate the intrinsic structure of a language to the structure of the representation. Contexts are easily observable from a sample and moreover it is only when the features correspond to the contexts that distributional learning algorithms can infer the structure of the language.

f G {(λ,b),(λ,abb)} {(λ,b),(λ,abb)} {(a,λ),(aab,λ)} {(a,λ),(aab,λ)} f G f G f G Rule: (λ,λ) → (λ,b) (aab,λ) f G (ab) Ù {(λ,λ)} Rule: (a,λ) → (λ,λ) (aab,λ) f G (abb) Ù {(a,λ)} Rule: (λ,λ) → (λ,abb) (a,λ) f G (aabb) Ù {(λ,λ)} f G {(λ,b),(λ,abb)} {(λ,b),(λ,abb)} {(a,λ),(aab,λ)} {(a,λ),(aab,λ)} f G f G f G Rule: (λ,λ) → (λ,abb) (a,λ) f G (ab) Ù {(λ,λ)} Rule: (λ,b) → (λ,abb) (λ,λ) f G (aab) Ù {(λ,b)} Rule: (λ,λ) → (λ,b) (aab,λ) f G (aabb) Ù {(λ,λ)} Figure 1:
The two derivations to obtain (λ, λ) in f G (aabb) in the grammar G.

A Parsing Example

To clarify the relationship with CFG parsing, we will give a simple worked example. Consider the CBFG G = {(λ, λ), (aab, λ), (λ, b), (λ, abb), (a, λ)}, P, P L , {a, b} with

P L = { {(λ, b), (λ, abb)} → a, {(a, λ), (aab, λ)} → b }. and P = { {(λ, λ)} → {(λ, b)}{(aab, λ)}, {(λ, λ)} → {(λ, abb)}{(a, λ)}, {(λ, b)} → {(λ, abb)}{(λ, λ)}, {(a, λ)} → {(λ, λ)}{(aab, λ)} }.
If we want to parse a string w the usual way is to have a bottom-up approach. This means that we recursively compute the f G function on the substrings of w in order to check whether (λ, λ) belongs to f G (w).

For example, suppose w = aabb. Figure 1 graphically gives the main steps of the computation of f G (aabb). Basically there are two ways to split aabb that allow the derivation of the empty context: aab|b and a|abb. The first one corresponds to the top part of the figure while the second one is drawn at the bottom. We can see for instance that the empty context belongs to f G (ab) thanks to the rule

{(λ, λ)} → {(λ, abb)}{(a, λ)}: {(λ, abb)} ⊆ f G (a) and {(a, λ)} ⊆ f G (b)
. But for symmetrical reasons the result can also be obtained using the rule

{(λ, λ)} → {(λ, b)}{(aab, λ)}.
As we trivially have f G (aa) = f G (bb) = ∅, since no right-hand side contains the concatenation of the same two features, an induction proof can be written to show that

(λ, λ) ∈ f G (w) ⇔ w ∈ {a n b n : n > 0}.
This is a simple example that illustrates the parsing of a string given a CBFG. This example does not fully express the power of CBFG since no element of the right hand side of a rule is composed of more than one context. A more complex example, corresponding to a context-sensitive language, will be presented in Section 6.1.3.

We stop here the presentation of the CBFG formalism and we present our learning algorithm in the next section. However, if the reader wishes to become more familiar with CBFGs a study on their expressiveness is provided in Section 6.

Learning Algorithm

We have carefully defined the representation so that the inference algorithm will be almost trivial. Given a set of strings, and a set of contexts, we can simply write down a CBFG that will approximate a particular language.

Building CBFGs from Sets of Strings and Contexts

Definition 11 Let L be a language, F be a finite set of contexts such that (λ, λ) ∈ F , K a finite set of strings,

P L = {F L (u) → u|u ∈ K ∧ |u| = 1} and P = {F L (uv) → F L (u)F L (v)|u, v, uv ∈ K}.
We define G 0 (K, L, F ) as the CBFG F, P, P L , Σ .

Often K will be closed under substrings: i.e. Sub(K) = K. This grammar is a CBFG, since K and F are finite, and so P and P L are too by construction. In general it will not be exact.

We will call K here the basis for the language. The set of productions is defined merely by observation: we take the set of all productions that we observe as the concatenation of elements of the small set K.

Let us explain the construction in more detail. P L is the set of lexical productionsanalogous to rules of the form N → a in a CFG in Chomsky normal form. These rules just assign to the terminal symbols their observed distribution -this will obviously be correct in that f G (a) = F L (a). P is the interesting set of productions: these allow us to predict the features of a string uv from the features of its part u and v. To construct P we take all triples of strings u, v, uv that are in our finite set K. We observe that u has the contexts F L (u) and v has the set of contexts F L (v): our rule then states that we can combine any string that has all of the contexts in F L (u) together with any string that has the contexts in F L (v) and the result will have all of the contexts in F L (uv).

We will now look at a simple example. Let L = {a n b n | n > 0}, F , the set of features is {(λ, λ), (a, λ), (λ, b)} and K, the basis, is {a, b, ab, aa, aab}. For each of the elements of K we can compute the set of features that it has:

• F L (a) is just {(λ, b)} -this is the only one of the three contexts in F such that f ⊙ a ∈ L. • F L (b) = {(a, λ)} • F L (aa) = ∅ • F L (ab) = {(λ, λ)} • F L (aab) = {(λ, b)}.
G 0 will therefore have the following lexical productions

P L = {(λ, b)} → a, {(a, λ)} → b.
We can now consider the productions in P . Looking at K we will see that there are only four possible triples of strings of the form uv, u, v: these are (aa, a, a), (ab, a, b), (aab, aa, b) and (aab, a, ab). Each of these will give rise to an element of P :

• The rule given by ab = a • b: {(λ, λ)} → {(λ, b)}{(a, λ)}, • aa = a • a gives ∅ → {(λ, b)}{(λ, b)}, • aab = aa • b gives {(λ, b)} → ∅{(a, λ)}, • aab = a • ab gives {(λ, b)} → {(λ, b)}{(λ, λ)}.
Given K, F and an oracle for L we can thus simply write down a CBFG. However, in this case, the language L(G 0 ) is not the same as L; moreover, the resulting grammar is not exact. Applying the rules for the recursive computation of f G , we can see that

f G 0 (aab) = {(λ, b)} and f G 0 (abb) = f G 0 (aabb) = {(λ, b), (λ, λ)} but F L(G 0 ) (abb) = {(a, λ), (λ, b), (λ, λ)}
and thus G 0 is not exact. The problem here is caused by the fact that the production {(λ, b)} → ∅{(a, λ)} allows any string to occur in the place specified by the ∅: indeed since ∅ ⊆ f G 0 (aab) and {(a, λ)} ⊆ f G 0 (b) the rule holds for aabb and thus {(λ, b)} ⊆ f G 0 (aabb). This is actually caused by the fact that there are no contexts in F that correspond to the string aa in K.

Fixing L for the moment, clearly the language defined depends on two factors: the set of strings K and the set of features F . Given K and F , and access to a membership oracle, we can write down a CBFG with almost no computation, but we still have the problem of finding suitable K and F -it might be that searching for exactly the right combination of K and F is intractably hard. It turns out that it is also very easy to find suitable sets.

In the next section we will establish two important lemmas that show that the search for K and F is fundamentally tractable: first, that as K increases the language defined by G 0 (K, L, F ) will increase, and secondly that as F increases the language will decrease. Let us consider one example that illustrates these properties. Consider the language

L = {a n b | n ≥ 0} ∪ {ba m | m ≥ 0} ∪ {a}.
First, let K = {a, b, ab} and F = {(λ, λ)}; then, by the definition of G 0 , we have the following productions:

• {(λ, λ)} → a • {(λ, λ)} → b • {(λ, λ)} → {(λ, λ)}{(λ, λ)}.
It is easy to see that L(G 0 ) = Σ + . Now, suppose that F = {(λ, λ), (λ, b)} with K unchanged; then, by construction G 0 will have the following productions:

• {(λ, λ), (λ, b)} → a, • {(λ, λ)} → b, • {(λ, λ)} → {(λ, λ), (λ, b)}{(λ, λ)}.
The language defined by G 0 contains a n b and also a n since {(λ, λ)} ⊂ {(λ, λ), (λ, b)} allowing the third production to accept strings ending with an a. Thus, the language has been reduced such that

L(G 0 ) = {a n b | n ≥ 0} ∪ {a m | m ≥ 0}.
We continue by leaving F = {(λ, λ), (λ, b)} and we enlarge K such that K = {a, b, ab, ba}. The productions in G 0 are:

• {(λ, λ), (λ, b)} → a, • {(λ, λ)} → b, • {(λ, λ)} → {(λ, λ), (λ, b)}{(λ, λ)}; the rule given by ab = a • b, • {(λ, λ)} → {(λ, λ)}{(λ, λ), (λ, b)}; the rule given by ba = b • a.
The addition of the last rule allows the grammar to recognize ba n and it can be easily shown that by a combination of the last two productions a n ba m belongs to the language defined by the grammar. Then, L(G 0 ) has been increased such that

L(G 0 ) = {a n ba k | n, k ≥ 0} ∪ {a m | m ≥ 0}.
In this example, the addition of (λ, b), (a, λ) and (λ, a) to F and the addition of aab and baa to K will then define the correct language. In fact this illustrates one principle of our approach: in the infinite data limit, the construction G 0 will define the correct language. In the following lemma we abuse notation and use G 0 for when we have infinite K, and F : in this lemma we let K be the set of all non-empty strings and we let F be the set of all possible contexts (Σ * × Σ * ). Recall that in this case for every string w C L (w) = F L (w).

Lemma 12 For any language L, let G = G 0 (Σ + , L, Σ * × Σ * ). Then for all w ∈ Σ + f G (w) = C L (w) and therefore L(G) = L.
Proof By induction on the length of w. If |w| = 1, and w = a then there is a lexical production C L (a) → a and by the definition of f G (a) = C L (a). Suppose this is true for all w with |w| ≤ k. Let w be some string of length k + 1. Consider any split of w into u, v such that w = uv. f G (w) is the union over all these splits of a function. We will show that every such split will give the same result of C L (w). By inductive hypoth-

esis f G (u) = C L (u), f G (v) = C L (v)
. Since u, v, w are in K = Σ + we will also have an element of P of the form C L (w) → C L (u)C L (v), so we know that f G (w) ⊇ F L (w). We now show that f G will not predict any extra contexts. Consider every production in P ,

F L (u ′ v ′ ) → F L (u ′ )F L (v ′ ), that applies to u, v, i.e. with F L (u ′ ) ⊆ f G (u) = C L (u) and F L (v ′ ) ⊆ f G (v) = C L (v).
Lemma 5 shows that in this case F L (u ′ v ′ ) ⊆ F L (w) and thus we deduce that f G (w) ⊆ F L (w), which establishes the lemma.

Informally if we take K to be every string and F to be every context, then we can accurately define any language. Of course, we are just interested in those cases where this can be defined finitely and we have a CBFG, in which case L will be decidable, but this infinite limit is a good check that the construction is sound.

Monotonicity Lemmas

We now prove two lemmas that show that the size of the language, and more particularly the features predicted will increase or decrease monotonically as a function of the basis K, and the feature set F , respectively. In fact, they give also a framework for approaching a target language from K and F .

Lemma 13 Suppose we have two CBFGs defined by

G = G 0 (K, L, F ) and G ′ = G 0 (K, L, F ′ ) where F ⊆ F ′ . Then for all u, f G (u) ⊇ f G ′ (u) ∩ F .
Proof Let G ′ have a set of productions P ′ , P ′ L , and G have a set of productions P, P L . Clearly if x → yz ∈ P ′ then x ∩ F → (y ∩ F )(z ∩ F ) is in P by the definition of G 0 , and likewise for P L , P ′ L . By induction on |u| we can show that any feature in

f G ′ (u) ∩ F will be in f G (u). The base case is trivial since F ′ L (a) ∩ F = F L (a); if it is true for all strings up to length k, then if f ∈ f G ′ (u) ∩ F ;
there must be a production in F ′ with f on the head. By the inductive hypothesis, the right hand sides of the corresponding production in P will be triggered, and so f must be in f G (u).

Corollary 14 Suppose we have two CBFGs defined by G = G 0 (K, L, F ) and

G ′ = G 0 (K, L, F ′ ) where F ⊆ F ′ ; then L(G) ⊇ L(G ′ ). Proof It is sufficient to remark that if u ∈ L(G ′ ) then (λ, λ) ∈ f G ′ (u) ⊆ f G (u) and thus u ∈ L(G).
Conversely, we can show that as we increase K, the language and the map f G will increase. This is addressed by the next lemma.

Lemma 15 Suppose we have two CBFGs defined by

G = G 0 (K, L, F ) and G ′ = G 0 (K ′ , L, F ) where K ⊆ K ′ . Then for all u, f G 0 (K,L,F ) (u) ⊆ f G 0 (K ′ ,L,F ) (u).
Proof Clearly the sets of productions of G 0 (K, L, F ) will be a subset of the set of productions of G 0 (K ′ , L, F ), and so anything that can be derived by the first can be derived by the second, again by induction on the length of the string.

A simple result is that when K contains all of the substrings of a word, then G 0 (K, L, F ) will generate all of the correct features for this word.

Lemma 16 For any string w, if Sub(w) ⊂ K, and let

G = G 0 (K, L, F ), then F L (w) ⊆ f G (w).
Proof By recursion on the size of w. Let G = G 0 (K, L, F ) = F, P, P L , Σ . First, notice that if w is of length 1 then we have F L (w) → w in P L and thus the lemma holds. Then suppose that |w| = k ≥ 2. Let u and v in Σ + be such that w = uv. As Sub(w) ⊂ K we have u, v in K. Therefore the rule F L (w) → F L (u)F L (v) belongs to P . As |u| < |w| and |v| < |w|, by recursion we get

F L (u) ⊆ f G (u) and F L (v) ⊆ f G (v).
Thus the rule can be applied and then

F L (w) ⊆ f G (w).
In particular if w ∈ L, and Sub(w) ⊆ K, then w ∈ L(G). This means that we can easily increase the language defined by G just by adding Sub(w) to K. In general we do not need to add every element of Sub(w) -it is enough to have one binary bracketing.

To establish learnability, we need to prove that for a target language L, if we have a sufficiently large F then L(G 0 (K, L, F )) will be contained within L and that if we have a sufficiently large K, then L(G 0 (K, L, F )) will contain L.

Fiducial Feature Sets and Finite Context Property

We need to be able to prove that for any K if we have enough features then the language defined will be included within the target language L. We formalise the idea of having enough features in the following way: Definition 17 For a language L and a string u, a set of features F is fiducial on

u if for all v ∈ Σ * , F L (u) ⊆ F L (v) implies C L (u) ⊆ C L (v).
Note that if F is fiducial on u and F ⊂ F ′ then F ′ is fiducial on u. Therefore we can naturally extend this to sets of strings.

Definition 18 For a language L and a set of strings K, a set of features F is fiducial on K if for all u ∈ K, F is fiducial on u.

Clearly, for any string w, C L (w) will be fiducial on w; but this is vacuous -we are interested in cases where there is a finite set of contexts which is fiducial for w, but where C L (w) is infinite. If u and v are both in K then having the same features means they are syntactically congruent. However if two strings, neither of which are in K, have the same features this does not mean they are necessarily congruent (for instance if

F L (v) = F L (v ′ ) = ∅).
For non finite state languages, the set of congruence classes will be infinite, and thus we cannot have a finite fiducial set for the set of all strings in Sub(L), but we can have a feature set that is correct for a finite subset of strings, or more generally for an infinite set of strings, if they fall into a finite number of congruence classes.

Let us consider our running example L = {a n b n |n > 0}. Take the string ab. C L (ab) is infinite and contains contexts of the form (λ, λ), (a, b), (aa, bb) and so on. Consider a set with just one of these contexts, say F = {(a, b)}. This set is clearly fiducial for ab, since the only strings that will have this context are those that are congruent to ab. Consider now the string aab; clearly {(λ, b)} is fiducial for aab, even though the string a, which is not congruent to aab also occurs in this context. Indeed, this does not violate fiduciality since C L (a) ⊃ C L (aab). However, looking at string a, {(λ, b)} is not fiducial, since aab has this context but does not include all the contexts of a such as, for example, (λ, abb).

In these trivial examples, a context set of cardinality one is sufficient to be fiducial, but this is not the case in general. Consider the finite language L = {ab, ac, db, ec, dx, ey}, and the string a. It has two contexts (λ, b) and (λ, c) neither of which is fiducial for a on its own. However, the set of both contexts is: {(λ, b), (λ, c)} is fiducial for a.

We now define the finite context property, which is one of the two conditions that languages must satisfy to be learnable in this model; this condition is a purely language theoretic property.

Definition 19 A language L has the Finite Context Property (FCP) if every string has a finite fiducial feature set.

Clearly if L has the FCP, then any finite set of substrings, K, has a finite fiducial feature set which will be the union of the finite fiducial feature sets for each element of K. If u ∈ Sub(L) then any set of features is fiducial since C L (u) = ∅.

We note here that all regular languages have the FCP. We refer the reader to the Section 6.1.1 about CBFG and regular languages where the Lemma 35 and the associated construction proves this claim.

We can now state the most important lemma: this lemma links up the definition of the feature map in a CBFG, with the fiducial set of features to show that only correct features will be assigned to substrings by the grammar. It states that the features assigned by the grammar will correspond to the language theoretic interpretation of them as contexts.

Lemma 20 For any language L, given a set of strings K and a set of features F , let

G = G 0 (K, L, F ). If F is fiducial on K, then for all w ∈ Σ * f G (w) ⊆ F L (w).
Proof We proceed by induction on length of the string. Base case: strings of length 1. f G (w) will be the set of observed contexts of w, and since we have observed these contexts, they must be in the language. Inductive step: let w a string of length k.

Take a feature f on f G (w); by definition this must come from some production x → yz and a split u, v of w. The production must be from some elements of K, u ′ , v ′ and u

′ v ′ such that y = F L (u ′ ), z = F L (v ′ ) and x = F L (u ′ v ′ ). If the production applies this means that F L (u ′ ) = y ⊆ f G (u) ⊆ F L (u) (by inductive hypothesis), and similarly F L (v ′ ) ⊆ F L (v). By fiduciality of F this means that C(u ′ ) ⊆ C(u) and C(v ′ ) ⊆ C(v). So by Lemma 5 C(u ′ v ′ ) ⊆ C(uv). Since f ∈ C(u ′ v ′ ) then f ∈ C(uv) = C(w). Therefore, since f ∈ F and C(w) ∩ F = F L (w), f ∈ F L (w), and therefore f G (w) ⊆ F L (w). Corollary 21 If F is fiducial on K then L(G 0 (K, F, L)) ⊆ L.
Therefore for any finite set K from an FCP language, we can find a set of features so that the language defined by those features on K is not too big.

Kernel and Finite Kernel Property

We will now show a complementary result, namely that for a sufficiently large K the language defined by G 0 will include the target language. We will start by formalising the idea that a set K is large enough, by defining the idea of a kernel.

Definition 22 A finite set K ⊆ Σ * is a kernel for a language L, if for any set of features F , L(G 0 (K, F, L)) ⊇ L.

Consider again the language L = {a n b n |n ≥ 0}. The set K = {a, b, ab} is not a kernel, since if we have a large enough set of features, then the language defined will only be {ab} which is a proper subset of L. However K = {a, b, ab, aab, abb, aabb} is a kernel: no matter how large a set of features we have the language defined will always include L. Consider a language L ′ = L ∪ {b 16 }. In this case, a kernel for L ′ must include, as well as a kernel for L, some set of substrings of b 16 : it is enough to have b 16 , b 8 , b 4 , bb, b.

To prove that a set is a kernel, it suffices to show that if we consider all the possible features for building the grammar, we will contain the target language; any smaller set of features defines then a larger language. In our case, we can take the infinite set of all contexts and define productions based on the congruence classes. If F is the set of all contexts then we have F L (u) = C L (u), thus the productions will be exactly of the form C(uv) → C(u)C(v). This is a slight abuse of notation since feature sets are normally finite.

Lemma 23 Let F = Σ * × Σ * ; if L(G 0 (K, L, F )) ⊇ L then K is a kernel.
Proof By monotonicity of F : any finite feature set will be a subset of F . Not all context-free languages will have a finite kernel. For example L = {a + } ∪ {a n b m |n < m} is clearly context-free, but does not have a finite kernel. Assume that the set K contains all strings of length less than or equal to k. Assume w.l.o.g. that the fiducial set of features for K includes all features (λ, b i ), where i ≤ k + 1. Consider the rules of the form F L (a k ) → F L (a j )F L (a k-j ); we can see that no matter how large k is, the derived CBFG will undergenerate as a k is not congruent to a k-1 .

Definition 24 A context-free grammar G T = V, S, P, Σ has the Finite Kernel Property (FKP) iff for every non-terminal N ∈ V there is a finite set of strings K(N ) such that a ∈ K(N ) if a ∈ Σ and N → a ∈ P and such that for all k ∈ K(N ), N * ⇒ k and where for every string

w ∈ Σ * such that N * ⇒ w there is a string k ∈ K(N ) such that C(k) ⊆ C(w).
A CFL L has the FKP, if there is a grammar in CNF for it with the FKP.

Notice that all regular languages have the FKP since they have a finite number of congruence classes.

Lemma 25 Any context-free language with the FKP has a finite kernel.

Proof Let G T = V, S, P, Σ be such a CNF CFG with the FKP. Define

K(G T ) = N ∈V K(N ) ∪ X→M N ∈P K(M )K(N ) . (4)
We claim that K(G T ) is a kernel. Assume that F = Σ * × Σ * and let G be such that G = G 0 (K(G T ), L(G T ), F ) = F, (λ, λ), P, P L , Σ .

We will show, by induction on the length of derivation of w in G T , that for all N, w if N * ⇒ w then there is a k in K(N ) such that f G (w) ⊇ C(k). If length of derivation is 1, then this is true since |w| = 1 and thus w ∈ K(N ): therefore C(w) → w ∈ P L . Suppose it is true for all derivations of length less than j. Take a derivation of length j; say N * ⇒ w. There must be a production in G T of the form N → P Q, where P ⇒ * u and Q ⇒ * v, and w = uv. By inductive hypothesis; we have f

G (u) ⊇ C(k u ) and f G (v) ⊇ C(k v ). By construction k u k v ∈ K(G T )
and then there will be a rule

C(k u k v ) → C(k u )C(k v ) in P . Therefore f G (uv) ⊇ C(k u k v ). Since N * ⇒ k u k v there must be some k uv ∈ K(N ) such that C(k uv ) ⊆ C(k u k v ). Therefore f G (w) ⊇ C(k u k v ) ⊇ C(k uv ). Now we can see that if w ∈ L, then S * ⇒ w, then there is a k ∈ K(S) such that f G (w) ⊇ C(k) and S * ⇒ k, therefore (λ, λ) ∈ f G (w) since (λ, λ) ∈ C(k), thus w ∈ L(G)
and therefore K is a kernel.

Learning Algorithm

Before we present the algorithm, we will discuss the learning model that we use. The class of languages that we will learn is suprafinite and thus we cannot get a positive data only identification in the limit result [START_REF] Gold | Language identification in the limit[END_REF]. Ultimately we are interested in a more realistic probabilistic learning paradigm, but for mathematical convenience it is appropriate to establish the basic results in a symbolic paradigm. The ultimate goal is to model natural languages, where negative data, or equivalence queries are generally not available or are computationally impossible. Accordingly, we have decided to use the model of positive data together with membership queries: an oracle can tell the learner whether a string is in the language or not [START_REF] Angluin | Queries and concept learning[END_REF]. The presented algorithm runs in time polynomial in the size of the sample S: since the strings are of variable length, this size must be the sum of the lengths of the strings in S, w∈S |w|. We should note that this is not a strong enough result: [START_REF] Pitt | Inductive inference, dfa's, and computational complexity[END_REF] showed that any algorithm can be made polynomial, by only processing a small prefix of the data. It is hard to tighten the model sufficiently: the suggestion of de la Higuera (1997) for a polynomial characteristic set is inapplicable for representations, such as the ones in this paper, that are powerful enough to define languages whose shortest strings are exponentially long. Accordingly we do not require in this model a polynomial dependence on the size of the representation. We note that the situation is unsatisfactory, but we do not intend to propose a solution in this paper. We merely point out that the algorithm is genuinely polynomial and processes all of the data in the sample without "delaying tricks" of the type discussed by Pitt.

Definition 26 A class of languages L is identifiable in the limit (IIL) from positive data and a membership oracle with polynomial time and queries iff there exist two polynomials p(), q() and an algorithm A such that:

• Given an infinite presentation of positive examples S, where S n is the first n examples of the presentation, and S n has total size m, 1. A returns a representation G = A(S n ) in time p(m).

2. A asks at most q(m) queries to build A(S n ).

• For each language L ∈ L, for each presentation S of L, there exists an index n such that for all N ≥ n: A(S N ) = A(S n ) and L(A(S n )) = L.

K F K 0 Overgeneral Correct Undergeneral Wrong Figure 2:
The relationship between K and F : The diagonal line is the line of fiduciality: above this line means that F is fiducial on K. K 0 is a kernel for the language.

Before we present the algorithm we hope that it is intuitively obvious how the approach will work. Figure 2 diagrammatically shows the relationship between K and F . When we have a large enough K, we will be to the right of the vertical line; when we have enough features for that K we will be above the diagonal line. Thus the basis of the algorithm is to move to the right, until we have enough data, and then to move up vertically, increasing the feature set until we have a fiducial set.

We can now define our learning algorithm in Algorithm 1. Informally, D is the list of all strings that have been seen so far and G n is the current grammar obtained with the first n strings of D. The algorithm uses two tests: one test is just to determine if the current hypothesis undergeneralises. This is trivial, since we have a positive presentation of the data, and so eventually we will be presented with a string in L \ L(G n ). In this case we need to increase K; we accordingly increase K to the set of all substrings that we have observed so far. The second test is a bit more delicate. We want to detect if our algorithm overgeneralises. This requires us to search through a polynomially bounded set of strings looking for a string that is in L(G n ) \ L. An obvious candidate set is Con(D) ⊙ Sub(D); but though we conjecture that this is adequate, we have not yet been able to prove that is correct, as it might be that the overgenerated string does not lie in Con(L) ⊙ Sub(L).

Here we use a slightly stricter criterion: we try to detect whether F is fiducial for K: we search through a polynomially bounded set of strings, Sub(D), to find a violation of the fiduciality condition. If we find such a violation, then we know that F is not fiducial for K, and so we increase F to the set of all contexts that we have seen so far, Con(D).

In Algorithm 1, G 0 (K, O, F ) denotes the same construction as G 0 (K, L, F ), except that we use membership queries with the oracle O to compute F L for each element in K. We give the identification in the limit version of the algorithm, i.e. that admits an infinite positive presentation of strings in input.

Algorithm 1: CBFG learning algorithm IIL

Data:

A sequence of strings S = {w 1 , w 2 . . . , }, membership oracle O Result: A sequence of CBFGs G 1 , G 2 , . . . K ← ∅ ; D ← ∅ ; F ← {(λ, λ)} ; G = G 0 (K, O, F ) ; for w i do D ← D ∪ {w i }; C ← Con(D); S ← Sub(D); if ∃w ∈ D \ L(G) then K ← S ; F ← C ; end else if ∃v ∈ S, u ∈ K, f ∈ C such that F L (u) ⊆ F L (v) and f ⊙ u ∈ L but f ⊙ v ∈ L then F ← C ; end G = G 0 (K, O, F ) ; Output G i = G ; end
Theorem 27 Algorithm 1 runs in polynomial time in the size of the sample, and makes a polynomial number of calls to the membership oracle.

Proof The value of D will just be the set of observed strings; Sub(D) and Con(D) are both polynomially bounded by the size of the sample, and therefore so are |K| and |F |. Therefore the number of calls to the oracle is clearly polynomial, as it is bouned by |K||F |. Computing G 0 is also polynomial, since |P | ≤ |K| 2 , and all strings involved are in Sub(D).

Identification in the limit result

In the following, we consider the class of context-free languages having the FCP and the FKP, represented by CBFG. K n denotes the value of K at the n th loop, and similarly for F , D.

Definition 28 L CF G is the class of all context-free languages that satisfy the FCP and the FKP.

In what follows we assume that L is an element of this class, and that w 1 , . . . , w n , . . . is a infinite presentation of the language. The proof is straightforward and merely requires an analysis of a few cases. We will proceed as follows: there are 4 states that the model can be in, that correspond to the four regions of the diagram in Figure 2.

1. K is a kernel and F is fiducial for K; in this case the model has converged to the correct answer. This is the region labeled correct in Figure 2.

2. K is a kernel and F is not fiducial for K: then L ⊆ L(G), and at some later point, we will increase F to a fiducial set, and we will be in state 1: this is the region labeled overgeneral.

3. K is not a kernel and F is fiducial. Either L(G) = L, in which case we have converged to a correct answer or, if not, we will define a proper subset of the target language. In the later case we will change hypothesis at some later point, increase K to a kernel, and move to state 2 or state 1. This is the area labeled undergeneral.

4. K is not a kernel and F is not fiducial: in this case at some point we will move to states 1 or 2. This is the area labeled wrong.

We will start by making some basic statements about properties of the algorithm:

Lemma 29 If there is some n, such that F n is fiducial for K n and L(G n ) = L, then the algorithm will not change its hypothesis: i.e. for all n > N ,

K n = K N , F n = F N and therefore G n = G N .
Proof If L(G n ) is correct, then the first condition of the loop will never be met; if F n is fiducial for K n , then the second condition will never be satisfied.

Lemma 30 If there is some N such that K N is a kernel, then for all n > N ,

K n = K N .
Proof Immediate by definition of a kernel, and of the algorithm.

We now prove that if F is not fiducial then the algorithm will be able to detect this.

Lemma 31 If there is some n such that F n is not fiducial for K n , then there is some index n ′ ≥ n at which F n will be increased.

Proof If F n is not fiducial, then by definition there is some

u ∈ K, v ∈ Σ + such that F L (u) ⊆ F L (v), but there is an f ∈ C L (u) that is not in C L (v)
. By construction F L (u) is always non-empty, and so is F L (v). Thus v ∈ Sub(L). Note f ⊙ u ∈ L, so f ∈ Con(L). Let n ′ be the smallest index such that v ∈ Sub(D n ) and f ∈ Con(D n ): at this point, either F n will have changed, or not, in which case it will be increased at this point.

We now prove that we will always get a fiducial feature set.

Lemma 32 For any n, there is some n ′ such that F n ′ is fiducial for K n . 2. Suppose w 2 = aabb. D = {ab, aabb}. This is not in L(G 1 ) so we set b, ab, aa, bb, aab, abb, aabb}. We then have the following productions:

• K = Sub(D) = {a,
• F = Con(D) = {(λ,
• F L (ab) → F L (a), F L (b) which is {(λ, λ), (a, b)} → {(a, bb), (λ, abb), (λ, b)}, {(aa, b), (aab, λ), (a, λ)} • F L (aab) → F L (a), F L (ab) which is {(a, bb), (λ, b)} → {(a, bb), (λ, abb), (λ, b)}, {(λ, λ), (a, b)} • F L (aab) → F L (aa), F L (b) which is {(a, bb), (λ, b)} → {(λ, bb)}, {(aa, b), (aab, λ), (a, λ)} • F L (bb) → F L (b), F L (b) which is {(aa, λ)} → {(aa, b), (aab, λ), (a, λ)}, {(aa, b), (aab, λ), (a, λ)} • F L (aa) → F L (a), F L (a) which is {(λ, bb)} → {(a,
• F L (aabb) → F L (aa), F L (bb) which is {(λ, λ), (a, b)} → {(λ, bb)}, {(aa, λ)} • F L (aabb) → F L (aab), F L (b) which is {(λ, λ), (a, b)} → {(a, bb), (λ, b)}, {(aa, b), (aab, λ), (a, λ)} • F L (abb) → F L (a), F L (bb) which is {(aa, b), (a, λ)} → {(a, bb), (λ, abb), (λ, b)}, {(aa, λ)} • F L (abb) → F L (ab), F L (b) which is {(aa, b), (a, λ)} → {(λ, λ), (a, b)}, {(aa, b), (aab, λ), (a, λ)}
and the two lexical productions:

• F L (a) → a which is {(a, bb), (λ, abb), (λ, b)} → a • F L (b) → b which is {(aa, b), (aab, λ), (a, λ)} → b.
K is now a kernel and L(G) = L, but F is not fiducial for K, since (λ, bb) is not fiducial for aa (consider aaab).

3. Suppose w 3 = aaabbb. Now |Con(D 3 )| = 21; there are now several elements of Con(D 3 ) that are similar. For example (λ, λ), (a, b) and (aa, bb) are identical but as it is harmless for the resulting grammar, it does not mind. Now we will detect that F is not fiducial: we will find v = aaab, u = aa and f = (λ, abbb); F L (aa) = {(λ, bb)} = F L (aaab), but f ⊙ aaab = aaababbb which is not in L. We will therefore increase F to be Con(D 3 ), and then the algorithm will have converged. The final grammar will have 10 productions and 2 lexical productions; |K| = 8 and |F | = 21.

Practical Behavior of the Algorithm

In this section, we propose to study the behavior of our algorithm from a practical point of view. We focus more specifically on two important issues. The first one deals with the learning ability of the algorithm when the conditions for the theoretical learning result are not reached. Indeed, although the identification in the limit paradigm proves that with sufficient data it is possible to obtain exact convergence, it says nothing about the convergence when fewer learning examples are available: does the output get closer and closer to the target until it reaches it or does it stay far from the expected solution until receives enough data? The second question concerns the learning behavior of the algorithm: does it tend to over-generalise or to under-generalise?

For our experimental setup, we need to select appropriate datasets. In grammatical inference little has been done concerning benchmarking. The main available corpora are those of the on line competitions organised by the International Colloquium on Grammatical Inference. Three different competitions have recently taken place: the Abbadingo One [START_REF] Lang | Results of the abbadingo one dfa learning competition and a new evidence driven state merging algorithm[END_REF] which was about regular languages, the Omphalos competition on context-free languages [START_REF] Starkie | The omphalos context-free grammar learning competition[END_REF] and the Tenjino competition [START_REF] Starkie | The tenjinno machine translation competition[END_REF] dealing with transducers learning. Note that some of these datasets correspond to extremely hard learning problems since their main objective was to push the state of the art (some problems of the Abbadingo One competition are still unsolved more than ten years after its official end!) However, these datasets can not be directly used for evaluating our algorithm because the solutions or the target models are not available. Our algorithm needs an oracle and thus we need a way to give answers to membership queries. In order to overcome this drawback, we chose to build synthetically some data sets following the experimental setup proposed by these competitions. More precisely, we decided to randomly generate target context-free grammars following what has been done for the Omphalos competition. Each grammar is then used either to generate training and test sets or as an oracle for answering membership queries.

In the following paragraphs we describe first the generation of the target context-free grammars, then the experimental setup with learning and test datasets used and finally the results and conclusions that can be drawn.

Generation of Target Context-free Grammars

To generate the target grammars we follow the process used for the Omphalos competition [START_REF] Starkie | The omphalos context-free grammar learning competition[END_REF]. We built 50 different grammars randomly according the following principles. For each grammar, we first fix the number of non-terminals and terminals which are randomly chosen between 4 and 7 for the non-terminals (including the start symbol) and between 2 and 4 for terminal symbols. Then we randomly generate 20 context-free rules in Chomsky normal form such that every non-terminal appears at least once in the left hand side of a grammar rule. In order to avoid the presence of useless rules, we apply two simple procedures: if a non-terminal can not generate any terminal string, a new terminal rule generating one terminal symbol is created for this non-terminal; if a non-terminal can not be reached from the start symbol, we erase it from the grammar (i.e. we remove all the rules containing this non-terminal). From these grammars without useless rules, we force them to generate non finite languages by checking that the start symbol is used at least once in a right hand side of a grammar rule (in average this symbol appears in a right hand side of a rule more than 3 times per grammar).

The main difference with the Omphalos generation process is that we do not especially need non-regular languages. Indeed, one of the aim of these experiments is to give an idea on the behavior of the algorithm when its theoretical assumptions are not likely to be valid. From this standpoint, all randomly generated non-finite languages are good candidates as learning targets. However, with a similar principle used for the Omphalos competition, we checked that some of the generated grammars can not be easily solved by methods for regular languages. Although we can not decide if these grammars define non regular context-free languages, it ensures us that the target models are at least not too simple.

Experimental Setup

For each target grammar we generate a learning and a test sample following the Omphalos competition requirements. We build the learning sample by first creating a structurally complete set of strings for each grammar. This set is built such that for each rule of the target grammar, at least one string of the set can be derived using this rule [START_REF] Parekh | An incremental interactive algorithm for regular grammar inference[END_REF]. This would guarantee that the complete learning set would have the minimal amount of information for finding the structure of the grammar. We then complete this learning set by randomly generating new strings from the grammar in order to have a total of 50 examples. We chose arbitrarily this value for two reasons: first it is sufficient to ensure that each sample contains strictly a structurally complete set for each target grammar and secondly we are likely to be far from the guarantees of the identification in the limit framework.

The construction of the test set needs particular attention. Since the learning phase uses a membership oracle, when the hypothesis is being constructed, some new strings may be built and queried for the oracle by picking a prefix, a substring and a suffix from the learning sample. Thus, even if the test set does not contain any string of the learning sample, the construction G 0 may consider some strings present in the test set. In order to avoid this drawback, i.e. to guarantee that no string of the test could be seen during the construction of the CBFG, each test string has a length of at least 3 times the maximal length of the strings in the learning set. According to this procedure, we randomly generate a test set of 1000 strings over the alphabet of terminal symbols used to define the target grammar (1000 examples is twice the size of the small test sets of the Omphalos competition). The test sequences are then labeled positive or negative depending on their membership to the language defined by the grammar. We repeat this process until we have the desired number of strings. The ratio between strings in the language and strings outside the language is fixed to be between 40% and 60%.

In order to study the behavior of our algorithm, we define the following setup. For each target context-free grammar, we construct a CBFG by applying the construction G 0 (K, O, F ) with K = Sub(S) and F = Con(S) where S is a set of strings drawn from the learning set and using the target grammar as the oracle O for the membership queries. We generate different sets S by drawing an increasing number of learning examples (from 2 to 50) from the learning sample of the considered grammar. Then, we evaluate the learned CBFG on the test sample by measuring the accuracy of correct classification. We present the results averaged on the 50 test sets of the different target context-free grammars.

Results and Discussion

Figure 3 shows the averaged accuracy over the different target grammars according to the number of strings in the learning sample. We can note that a high correct classification rate (nearly 90%) is reached with 20 examples and with only 5 examples an accuracy of 75% is obtained. These results indicate that a relevant hypothesis can be found even with few examples. The standard deviations represented by vertical bars show a good stability of the results from learning sets of 20 strings. This confirms that our algorithm is able to learn partly correct representations even when learning sets may not have a kernel or a fiducial learning set and thus are far from the identification in the limit assumptions.

The analysis of the behavior of the algorithm in terms of false positive and false negative rates is shown in Table 5.3. The proportion of false negatives (i.e. positive strings classified as negative) is higher than the proportion of false positives (i.e. negative strings classified as positive), whatever the size of the learning sample is. Thus the output of the algorithm tends more to under-generalise than the converse. As it is generally admitted that overgeneralisation is the main trouble when learning from positive examples, this tendency confirms that the algorithm behaves well. However, it is difficult to draw firm conclusions without a natural distribution over negative examples.

The preceding results show that despite its simplicity the algorithm behaved nicely during these experiments, in particular concerning over-generalisation. We focus now on the amount of queries needed by the algorithm for building the CBFG. The growth of the number of requested queries according to the average size of the learning sample is shown in Figure 4 (recall that here the size of the sample means the sum of the string lengths of the sample). While a very worst case analysis of the grammar construction used by G 0 would lead to a complexity in O(|S| 5 ), we can observe that the number of queries seems to be quadratic, at least in the case of the grammars we consider here. However, the volume of queries used is large, which can be explained by the simplicity of the algorithm. From a practical standpoint, it is clear that much work has to be done in order to try to minimise the number of queries needed by selecting the most informative examples, but this point is 03.8 % ± 2.9 22.4 % ± 8.4 15 03.9 % ± 2.6 14.1 % ± 6.6 20 04.1 % ± 3.0 09.4 % ± 6.1 30 04.2 % ± 2.8 07.9 % ± 5.5 40 03.9 % ± 2.6 05.6 % ± 4.7 50 04.4 % ± 1.6 04.8 % ± 3.9

Table 1: Average percentage of false positive and false negative rates obtained over the test samples.

out of the scope of the paper.

Finally, we can note that these experiments suffer of the lack of comparison with other approaches. This is due to the fact that, as far as we know, no other algorithm uses a positive learning sample and a membership oracle only. Indeed, since the work of Angluin about the Minimum Adequate Teacher [START_REF] Angluin | Queries and concept learning[END_REF] all algorithms using membership queries are designed with the additional help of equivalence queries. The point of view adopted in this

(x)=x^4 f(x)=x^3 f(x)=x^2
Figure 4: Growth of the number of membership queries versus the average of the total size of the learning sample (using log log scale).

paper is rather theoretical since our aim was to show the relevance of CBFG representations for language learning. However, a perspective of our work is to try to avoid the use of the oracle (by using statistical or simulation methods) which will allow us to compare more easily our approach with other methods.

Expressiveness of CBFG

In this section, we compare the expressiveness of CBFG with other well known representations. As noted earlier, we are primarily interested in the class of exact CBFGs -these are CBFGs where the presence of a contextual feature in the representation corresponds exactly to the language theoretic interpretation of the context. The class of unrestricted CBFG is significantly larger, but less relevant.

The algorithm presented in this paper cannot learn the entire class of exact CBFGs, but we conjecture that there are more powerful algorithms that can; see [START_REF] Clark | A learnable representation for syntax using residuated lattices[END_REF] for some steps in this direction.

Exact CBFGs and the Chomsky Hierarchy

We start by examining the class of languages defined by exact CBFGs. We will show that this class

• includes all regular languages

• does not include all context free languages • includes some non-context-free languages.

This class is thus orthogonal to the Chomsky hierarchy.

Regular Languages

Any regular language can be defined by an exact CBFG. We will show a way of constructing an exact CBFG for any regular language. Suppose we have a regular language L: we consider the left and right residual languages:

u -1 L = {w|uw ∈ L}, (5)
Lu -1 = {w|wu ∈ L}. (6)
For any u ∈ Σ * , let l min (u) be the lexicographically shortest element such that l -1 min L = u -1 L. The number of such l min is finite by the Myhill-Nerode theorem, we denote by L min this set, i.e. {l min (u)|u ∈ Σ * }. We define symmetrically R min for the right residuals (Lr -1 min = Lu -1 ).

We define the set of contexts as:

F (L) = L min × R min . (7)
F (L) is clearly finite by construction. By considering this set of features, we can prove the following lemma:

Lemma 35 For any strings u, v such that F L (u) ⊃ F L (v) then C L (u) ⊃ C L (v).
Proof Suppose F L (u) ⊃ F L (v) and let (l, r) be a context in C L (v). Let l ′ be the lexicographically shortest element of {u : u -1 L = l -1 L} and r ′ the lexicographically shortest element of {u : Lu -1 = Lr -1 }. By construction we have (l ′ , r ′ ) ∈ F (L) and l ′ vr ′ ∈ L, as

vr ′ ∈ l ′-1 L = l -1 L. F L (v) is contained in F L (u) therefore we have l ′ ur ′ ∈ L. l ′-1 L = l -1 L implies lur ′ ∈ L. As r ′ is congruent to r, lur ∈ L.
This lemma means that the set of features F is sufficient to represent context inclusion.

Note that the number of congruence classes of a regular language is finite. Each congruence class is represented by a set of contexts F L (u). Let K L be finite set of strings formed by taking the lexicographically shortest string from each congruence class. The final grammar can be obtained by combining elements of K L . For every pair of strings u, v ∈ K L , we define a rule

F L (uv) → F L (u)F L (v) (8)
and we add lexical productions of the form F L (a) → a, a ∈ Σ.

The following lemma shows the correctness and the exactness of the grammar.

Lemma 36 For all w ∈ Σ * , f G (w) = F L (w).

Proof (Sketch) The proof is in two steps: f G (w) ⊆ F L (w) and F L (w) ⊆ f G (w). Each step is made by induction on the length of w and uses the rules created to build the grammar, the derivation process of a CBFG and the fiduciality for the second step. First, we show ∀w ∈ Σ * , f g (w) ⊆ F L (w) by induction on the length of w. For |w| = 1, the inclusion is trivial since all the lexical rules F L (a) → a are included in the grammar. Suppose that a string w, |w| = n > 1, is parsed by the CBFG G, then there exists a cut of w in uv = w and a rule z → xy in G such that x ⊆ f G (u) and y ⊆ f G (v). By induction hypothesis, x ⊆ F L (u) and y ⊆ F L (v). By construction of the grammar, there exists two strings u ′ , v ′ ∈ K L such that u, resp. v, belongs to same congruence class than u ′ , resp. v ′ and the rule F L (u ′ v ′ ) → F L (u ′ )F L (v ′ ) belongs to the productions of the grammar. By induction hypothesis, x ⊆ F L (u) = F L (u ′ ) and y ⊆ F L (v) = F L (v ′ ) and thus f G (w) ⊆ F L (w). Second, we prove that ∀w ∈ Σ * , F L (w) ⊆ f G (w) by induction on the length of w. The key point relies on the fact that when a string w is parsed by a CBFG G, there exists a cut of w into uv = w (u, v ∈ Σ * ) and a rule z → xy in G such that x ⊆ f G (u) and y ⊆ f G (v). The rule z → xy is also obtained from a substring from the set used to build the grammar using the F L function. By the inductive hypothesis we obtain inclusion between f G and F L on u and v.

For the language of Figure 5, the following set is sufficient to build an exact CBFG: {a, b, aa, ab, ba, aab, bb, bba} (this corresponds to all the substrings of aab and bba). We have:

F L (a) = F (L)\{(λ, λ), (a, λ)} → a, F L (b) = F (L) → b, F L (aa) = F L (a) → F L (a)F L (a), F L (ab) = F (L) → F L (a)F L (b) = F L (a)F (L), F L (ba) = F (L) → F L (b)F L (a) = F (L)F L (a), F L (bb) = F (L) → F L (b)F L (b) = F (L)F (L), F L (aab) = F L (bba) = F L (ab) = F L (ba).
The approach presented here gives a canonical form for representing a regular language by an exact CBFG. Moreover, this is is complete in the sense that every context of every substring will be represented by some element of F : this CBFG will completely model the relation between contexts and substrings.

Exact CBFGs do not include all CFLs

First, it is clear that the class of exact CBFGs includes some non-regular context-free languages: the grammar defined in Section 3.3 is an exact CBFG for the context-free and non regular language {a n b n |n > 0}, showing the class of exact CBFG has some elements properly in the class of CFGs.

We give now a context-free language L that can not be defined by an exact CBFG:

L = {a n b|n > 0} ∪ {a n c m |m > n > 0}.
Suppose that there exists an exact CBFG that recognizes it and let N be the length of the biggest feature (i.e. the longest left part of the feature). For any sufficiently large k > N , the sequences c k and c k+1 share the same features:

F L (c k ) = F L (c k+1 ). Since the CBFG is exact we have F L (b) ⊆ F L (c k ).
Thus any derivation of a k+1 b could be a derivation of a k+1 c k which does not belong to the language. However, this restriction does not mean that the class of exact CBFG is too restrictive for modeling natural languages. Indeed, the example we have given is highly unnatural and such phenomena appear not to occur in attested natural languages.

CBFG and Non Context-Free Languages

CBFGs are more powerful than CFGs in two respects. First, CBFGs can compactly represent languages like the finite language of all n! permutations of an n-letter alphabet, that have no concise representation as a CFG [START_REF] Asveld | Generating all permutations by context-free grammars in Chomsky normal form[END_REF]. Secondly, as we now show, there are some exact CBFGs that are not context-free. In particular, we define a language closely related to the MIX language (consisting of strings with an equal number of a's, b's and c's in any order) which is known to be non context-free, and indeed is conjectured to be outside the class of indexed grammars [START_REF] Boullier | Counting with range concatenation grammars[END_REF].

Let M = {{a, b, c} + }, the set of all strings of length at least one that can be built on the alphabet {a, b, c}. We consider now the language

L = L abc ∪ L ab ∪ L ac ∪ {a ′ a, b ′ b, c ′ c, dd ′ , ee ′ , f f ′ }: L ab = {wd|w ∈ M, |w| a = |w| b }, L ac = {we|w ∈ M, |w| a = |w| c }, L abc = {wf |w ∈ M, |w| a = |w| b = |w| c }.
In order to define a CBFG recognizing L, we have to select features (contexts) that can represent exactly the intrinsic components of the languages composing L. We propose to use the following set of features for each sublanguage:

• For L ab : (λ, d) and (λ, ad), (λ, bd).

• For L ac : (λ, e) and (λ, ae), (λ, ce).

• For L abc : (λ, f ′ ).

• For the letters a ′ , b ′ , c ′ , a, b, c we add: (λ, a), (λ, b), (λ, c), (a ′ , λ), (b ′ , λ), (c ′ , λ).

• For the letters d, e, f, d ′ , e ′ , f ′ we add; (λ, d ′ ), (λ, e ′ ), (λ, f ′ ), (d, λ), (e, λ), (f, λ).

Here, L ab will be represented by (λ, d), but we will use (λ, ad), (λ, bd) to define the internal derivations of elements of L ab . The same idea holds for L ac with (λ, e) and (λ, ae), (λ, ce).

For the lexical rules and in order to have an exact CBFG, note the special case for a, b, c:

{(λ, bd), (λ, ce), (a ′ , λ)} → a {(λ, ad), (b ′ , λ)} → b {(λ, ae), (c ′ , λ)} → c
For the nine other letters, each one is defined with only one context, for example using the rule {(λ, d ′ )} → d.

For the production rules, the most important one is: (λ, λ) → {(λ, d), (λ, e)}, {(λ, f ′ )}. Indeed, this rule, with the presence of two contexts in one of categories, means that an element of the language has to be derived so that it has a prefix u such that f G (u) ⊇ {(λ, d), (λ, e)}. This means u is both an element of L ab and L ac . This rule represents the language L abc since {(λ, f ′ )} can only represent the letter f .

The other parts of the language will be defined by the following rules:

(λ, λ) → {(λ, d)}, {(λ, d ′ )}, (λ, λ) → {(λ, e)}, {(λ, e ′ )}, (λ, λ) → {(λ, a)}, {(λ, bd), (λ, ce), (a ′ , λ)}, (λ, λ) → {(λ, b)}, {(λ, ad), (b ′ , λ)}, (λ, λ) → {(λ, c)}, {(λ, ae), (c ′ , λ)}, (λ, λ) → {(λ, d ′ )}, {(d, λ)}, (λ, λ) → {(λ, e ′ )}, {(e, λ)}, (λ, λ) → {(λ, f ′ )}, {(f, λ)}.
This set of rules is incomplete, since for representing L ab , the grammar must contain the rules ensuring to have the same number of a's and b's, and similarly for L ac . To lighten the presentation here, the complete grammar is presented in Appendix.

We claim this is an exact CBFG for a context-sensitive language. L is not contextfree since if we intersect L with the regular language Σ * d, we get an instance of the non context-free MIX language (with d appended). The exactness comes from the fact that we chose the contexts in order to ensure that strings belonging to a sublanguage can not belong to another one and that the derivation of a substring will provide all the possible correct features with the help of the union of all the possible derivations.

Note that the MIX language on its own is not definable by an exact CBFG: it is only when other parts of the language can distributionally define the appropriate partial structures that we can get context sensitive languages. Far from being a limitation of this formalism (a bug), we argue this is a feature: it is only in rather exceptional circumstances that we will get properly context sensitive languages. This formalism thus potentially accounts not just for the existence of non context-free natural languages but also for their rarity.

Inexact CBFGs

We are less interested in the class of all CBFGs: these are CBFGs where the contexts are just arbitrary features and there is no relation between f G (u) and C L (u) except for the presence of (λ, λ). However, it is important to understand the language theoretic power of this class as this upper bounds the hypothesis class of the algorithm, and is easier to analyse.

Context-free grammars

First, we note that this class contains all context-free languages. Given a context-free language, that does not include the empty string, we can take a CFG in Chomsky normal form and convert it directly into a CBFG. Let V be the set of non-terminals of such a CFG. We pick an arbitrary set of distinct contexts to represent the elements of V , subject only to the constraint that S corresponds to (λ, λ). Let C(N ) be the context corresponding to the non-terminal N . For every production rule in the CFG of the form N → P Q, we add a CBFG production {C(N )} → {C(P )}, {C(Q)}. For every production in the CFG of the form N → a, we add a CBFG production to P L of the form {C(N )} → a. It is easy to see that this will define the same language.

Range Concatenation Grammars

While CBFG formalism has some relationship to a context-free grammar, and some to a semi-Thue system (also known as a string rewriting system), it is not formally identical to either of these. One exact equivalence is to a restricted subset of Range Concatenation Grammars; a very powerful formalism [START_REF] Boullier | A Cubic Time Extension of Context-Free Grammars[END_REF]. We include the following relationship, but suggest that the reader unfamiliar with RCGs proceeds to the discussion of the relationship with the more familiar class of context-free grammars.

Lemma 37 For every CBFG G, there is a non-erasing positive range concatenation grammar of arity one, in 2-var form that defines the same language.

Proof Suppose G = F, P, P L , Σ . Define a RCG with a set of predicates equal to F and the following clauses, and the two variables U, V . For each production x → yz in P , for each f ∈ x, where y = {g 1 , . . .

g i }, z = {h 1 , . . . h j } add clauses f (U V ) → g 1 (U ), . . . g i (U ), h 1 (V ), . . . h j (V ). For each lexical production {f 1 . . . f k } → a add clauses f i (a) → ǫ.
It is straightforward to verify that f (w) ⊢ ǫ iff f ∈ f G (w).

Conjunctive Grammar

A tighter correspondence is to the class of Conjunctive Grammars [START_REF] Okhotin | Conjunctive grammars[END_REF], invented independently of RCGs.

Definition 38 A conjunctive grammar is defined as a quadruple Σ, N, P, S , in which: Σ is the alphabet; N is the set of non terminal symbols; P is the set of rules, each of the form A → α 1 &...&α m , where A ∈ V and ∀i < m, α i ∈ (V ∪ Σ) * ; S ∈ N is the start symbol.

In this formalism, a string w is derived from A ∈ V iff there exists a rule A → α 1 &...&α m in P and for all i < m, α i derives w.

We claim that for every every language L generated by a conjunctive grammar there is a CBFG representing L# (where the special character # is not included in the original alphabet).

Suppose we have a conjunctive grammar G = Σ, N, P, S in binary normal form (as defined in [START_REF] Okhotin | An overview of conjunctive grammars. Formal Language Theory Column[END_REF]). We construct the equivalent CBFG G ′ = F, P ′ , P L , Σ as followed:

• For every letter a we add a context (l a , r a ) to F such that l a ar a ∈ L;

• For every rules X → a in P , we create a rule {(l a , r a )} → a in P L .

• For every non terminal X ∈ N , for every rule

X → P 1 Q 1 & . . . &P n Q n we add distinct contexts {(l P i Q i , r P i Q i )} to F, such that for all i it exists u i , l P i Q i u i r P i Q i ∈ L and P i Q i * ⇒ G u i ; • Let F X,j = {(l P i Q i , r P i Q i ) :
∀i} the set of contexts corresponding to the j th rule applicable to X. For all (l P i Q i , r P i Q i ) ∈ F X,j , we add to P ′ the rules (l P i Q i , r P i Q i ) → F P i ,k F Q i ,l (∀k, l).

• We add a new context (w, λ) to F such that S * ⇒ G w and (w, λ) → # to P L ;

• For all j, we add to P ′ the rule (λ, λ) → F S,j {(w, λ)}.

It can be shown that this construction gives an equivalent CBFG.

Discussion and Conclusion

One of the main objective of our approach is to provide a framework that helps to bridge the gap between theoretical methods of grammatical inference and the structured representations required in linguistics. We provide a conclusion and a discussion of our work according to these two standpoints.

Grammatical Inference

In this paper, we have presented a new formalism the Contextual Binary Feature Grammars and shown its relevance for representing a large class of languages. We have proposed a learning algorithm using only membership queries and shown that this algorithm can identify in the limit the class of context-free languages satisfying the FCP and FKP assumptions.

First of all, we should establish how large the class of languages with the FCP and the FKP is: it includes all finite languages and all regular languages, since the set of congruence classes is finite for finite state languages. It similarly includes the context-free substitutable languages, [START_REF] Clark | Polynomial identification in the limit of substitutable context-free languages[END_REF], since every string in a substitutable language belongs to only one syntactic congruence class. As already stated it does not include all CFLs since not all CFLs have the FCP and/or the FKP. However it does include languages like the Dyck languages of arbitrary order, Lukacevic language and most other classic simple examples. As a special case consider the equivalence relation between contexts f ∼ = L f ′ iff ∀u we have that f ⊙ u ∈ L iff f ′ ⊙ u ∈ L. The class of CFLs where the context distribution of every string is a finite union of equivalence classes of contexts clearly has both the FKP and the FCP.

If we now focus on the algorithm proposed: it is relatively simple but has two main drawbacks. First, the algorithm is not conservative since once we have found the correct language, the representation may change -if the feature set found is not fiducial -until the fiduciality is reached. Second, the CBFG output by the algorithm may not be consistent with some answers provided by the oracle. Indeed, when the algorithm checks the fiduciality of the feature set F , the membership of new strings is tested. These strings do not appear in the list of learning examples given to the oracle but are built from all the possible contexts and substrings that can be extracted from this list. Then, it is possible that, among these new strings, some of them belong to the target language but are not recognized by the current grammar. In this case, the output grammar is nevertheless not modified. We can imagine a procedure that changes the grammar by adding these new positive strings for building the CBFG, however this could lead to having to deal with an exponential number of strings. Thus, a more reasonable procedure is to wait for these strings in the positive data presentation. One proposal for future work, from these two remarks, is a new learning algorithm that overcomes these drawbacks.

One important point is whether this result can be extended to a result which also bounds the number of samples as a polynomial function of the size of the representation. A preliminary result in this direction is presented in [START_REF] Clark | Distributional learning of some context-free languages with a minimally adequate teacher[END_REF], which presents a polynomial result using the Minimally Adequate Teacher model of [START_REF] Angluin | Learning regular sets from queries and counterexamples[END_REF]. It seems likely that it will be possible to extend that result, which uses only context-free grammars, to the class of CBFGs.

Our approach to context-free grammatical inference is based on a generalisation of distributional learning, following the work of [START_REF] Clark | Polynomial identification in the limit of substitutable context-free languages[END_REF]. The current state of the art in context-free inductive inference from flat unstructured examples only has been rather limited. When learning from stochastic data or using a membership oracle, it is possible to have powerful results, if we allow exponential computation (see for example [START_REF] Horning | A Study of Grammatical Inference[END_REF]). The main contribution of this paper is to show that efficient learning is possible, with an appropriate representation. We currently rely on using a membership oracle, but under suitable assumptions about distributions, it should be possible to get a PAC-learning result for this class along the lines of [START_REF] Clark | PAC-learning unambiguous NTS languages[END_REF], placing some bounds on the number of features required. Another interesting and needed issue is the adaptation of this approach to stochastic languages.

We have focused on context-free grammatical inference, however, we have shown that our representation is also relevant for modeling non context-free languages. Then, another perspective of this work is to study learnability results for larger classes of languages. This would allow us to compare with other formalisms such as External Contextual Grammars [START_REF] Boullier | From contextual grammars to range concatenation grammars[END_REF][START_REF] Mitrana | Marcus external contextual grammars: From one to many dimensions[END_REF] and other learning methods dealing with non context-free languages [START_REF] Oates | Inferring grammars for mildly context sensitive languages in polynomial-time[END_REF][START_REF] Yoshinaka | Learning mildly context-sensitive languages with multidimensional substitutability from positive data[END_REF].

Linguistics

The field of grammatical inference has close relations to the study of language acquisition. Attempts to model natural languages with context-free grammars require additional machinery: natural language categories such as noun phrases contain many overlapping subclasses with features such as case, number, gender and similarly for verbal categories. Modelling this requires either an exponential explosion of the number of non-terminals employed or a switch to a richer set of features. Our formalism can be seen as a first step to integrate such features. While we have implemented the algorithm described here, and verified that it works in accordance with theory on small artificial examples, there are a number of modifications that would need to be made before it can be applied to real grammar induction on natural language. First, the algorithm is very naive; in practice a more refined algorithm could select both the kernel and the feature set in a more sophisticated way. Secondly, considering features that correspond to individual contexts may be too narrow a definition for natural language given the well known problems of data sparseness and it will be necessary to switch to features corresponding to sets of contexts, which may overlap. Thus for example one might have features that correspond to sets of contexts of the form F (u, v) = {(lu, vr)|l, r ∈ Σ * }. This would take this approach closer to methods that have been shown to be effective in unsupervised learning in NLP [START_REF] Klein | Corpus-based induction of syntactic structure: models of dependency and constituency[END_REF] where typically |u| = |v| = 1. In any event, we think such modifications will be necessary for the acquisition of non context-free languages. Finally, at the moment the algorithm has polynomial update time, but in the worst case, there are deterministic finite state automata such that the size of the smallest kernel will be exponential in the number of states. There are, however, natural algorithms for generalising the productions by removing features from the right hand sides of the rules; this would have the effect of accelerating the convergence of the algorithm, and removing the requirement for the Finite Kernel Property.

•

  F = Con(D) = {(λ, λ), (a, λ), (λ, b)}. This gives us one production: F L (ab) → F L (a)F L (b) which corresponds to {(λ, λ)} → {(λ, b)}{(a, λ)}, and the lexical productions {(λ, b)} → a, {(a, λ)} → b. The language defined is thus L(G 1 ) = {ab}.

  λ), (a, λ), (λ, b), (aa, λ), (a, b), (λ, bb), (aab, λ), (aa, b), (a, bb), (λ, abb)}.

  bb), (λ, abb), (λ, b)}, {(a, bb), (λ, abb), (λ, b)} • F L (aabb) → F L (a), F L (abb) which is {(λ, λ), (a, b)} → {(a, bb), (λ, abb), (λ, b)}, {(aa, b), (a, λ)}

  accuracy over the test sets Number of strings in the learning sample

Figure 3 :

 3 Figure 3: Evolution of the average percentage of correct classification according to the number of learning examples.

Figure 5 :

 5 Figure 5: Example of a DFA. The left residuals are defined by λ -1 L, a -1 L, b -1 L are the right ones by Lλ -1 , Lb -1 , Lab -1 (note here that La -1 = Lλ -1 ).

Note here that the word distributional does not refer to stochastic distributions, but to the occurrence of strings into contexts. The distribution of a string corresponds to all the possible contexts in which the string can appear.

This example does not account for a number of syntactic and semantic phenomena, particularly the distribution of reflexive anaphors.

Acknowledgments

This work was supported in part by the IST Programme of the European Community, under the PASCAL2 Network of Excellence, IST-2007-216886. This publication only reflects the authors' views.

We would like to thank Ryo Yoshinaka for very helpful discussions, and the anonymous reviewers for suggestions and comments that have greatly improved the paper. We also want to thank Jean-Marie Madiot who worked on the first version of the experiments presented in this paper.

Proof If F n is fiducial then n ′ = n satisfies the condition. Assume otherwise. Let F be a finite set of contexts that is fiducial for K n . We can assume that F ⊆ Con(L).

Let n 1 be the first index such that Con(D n 1 ) contains F . At this point we are not sure that F n 1 = Con(D n 1 ) since the conditions for changing the set of contexts may not be reached. Anyhow, if it is the case then F n 1 is fiducial, then n 1 = n ′ satisfies the condition. If not, then by the preceding lemma, there must be some point n 2 at which we will increase the set of contexts of the current grammar; F n 2 = Con(n 2 ) must contain F since Con(D n 1 ) ⊂ Con(D n 2 ), and is therefore fiducial, and so n 2 = n ′ satisfies the condition.

Lemma 33 For every positive presentation of an L ∈ L CF G , there is some n such that either the algorithm has converged to a correct grammar or K n is a kernel.

Proof Let m be the smallest number such that Sub(D m ) is a kernel. Recall that any superset of a kernel is a kernel, and that all CFL with the FKP have a finite kernel (Lemma 25), and that such a kernel is a subset of Sub(L), so such an m must exist.

Consider the grammar G m ; there are three possibilities: 1. L(G m ) = L, and F m is fiducial, in which case the grammar has converged.

will be increased to include Sub(D m ) and it will therefore be a kernel. 3. F m is not fiducial: in this case by Lemma 32; there is some n at which F n is fiducial for K m . Either K n = K m in which case this reduces to Case 2; or K n is larger than K m in which case it must be a kernel, since it will include Sub(D m ) which is a kernel.

We now can prove the main result of the paper:

Theorem 34 Algorithm 1 identifies in the limit the class of context-free languages with the finite context property and the finite kernel property.

Proof By Lemma 33 there is some point at which it converges or has a kernel. If K n is a kernel then by Lemma 32, there is some point n ′ at which we have a fiducial feature set. Therefore L(G n ′ ) = L, and the algorithm has converged.

Examples

We will now give a worked example of the algorithm.

Suppose L = {a n b n |n > 0}. G 0 will be the empty grammar, with K = ∅, F = {(λ, λ)} and an empty set of productions. L(G 0 ) = ∅.

1. Suppose w 1 = ab. D = {ab}. This is not in L(G 0 ) so we set

Appendix

We give here an explicit exact CBFG for the following non context-free language

Here is the list of productions of the grammar: