New Polynomial Bounds for the Identication inthe Limit Paradigm using Generative Grammars
Rémi Eyraud1 and Jerey Heinz2
QARMA team, Laboratoire d'Informatique Fondamentale, Marseilles, France
Dept. of Linguistics and Cognitive Science, University of Delaware, Newark, USA

12Complexity analysis in computer science examines worst-case scenarios. If
an algorithm solves a problem, are there instances of the problem space that
require the algorithm to consume an extraordinary amount of resources before
outputting their solutions?
This work deals with the open question about how to dene learning
paradigms in order to best analyze the complexity of learning algorithms, inthe particular case of algorithms that aim at learning formal languages. For
reasons that are mostly due to the type of models infered, the formalization ofidentication in the limit [3] is often used in this eld. Several renements ofGold's rst formalization have been dened with the aim to introduce eciency
bounds to strengthen learning results obtained in this identication in the limit
framework. A widely used one is named identication with polynomial time anddata [2], where the algorithm updates its hypothesis in a time polynomial in thesize of the available data, and is required to admit a characteristic sample whose
size is polynomial in the size of the learning target. (A sample S is characteristic
if the algorithm is ensured to converge to a representation of the learning target
on any sample containing S ).
However, there exist classes of languages identiable in the limit by algorithms which return representations that are exponentially smaller than theircharacteristic samples. There is an intuition that these algorithms, by nding
correct, compact representations of observed data are doing something right,
and that a denition of the complexity of learning algorithms should view suchalgorithms favorably.
This work proposes a modied paradigm. We dene structurally complete
sets and instead consider the property that a characteristic sample of a language L be polynomial in the size of a minimal structurally complete set for L.
While the previous renement is not centered on the target language but on its
selected representation, which is an important shift in perspective, this new formalization focuses the attention on the strings you can obtain using the target
representation.
Formally, the newly designed paradigm is dened as follows:Denition (Polynomial Structurally Complete Identication). A class

L of languages is identiable in polynomial time and structurally complete datafor a class R of representations if and only if there exist an algorithm A and two
polynomials p() and q() such that:1. Given a sample S for L ∈ L of size m, A returns a hypothesis H ∈ R inO(p(m)) time ;2. For each representation R of a language L ∈ L, there exists a characteristic
sample CS whose size is in O(q(k)), where k is the size of the smallest
structurally complete set for R.
Where a characteristic sample is a set of data such that on any sample that
contains it, the algorithm outputs an hypothesis that is correct. The notion ofstructurally complete set is the following:Denition (Structually Complete Set). Given a generative grammar G, astructurally complete set (SCS) for G is a set of data SC such that for eachproduction α → β , there exists an element x ∈ SC , an element γ ∈ I and twoelements η, τ ∈ (Σ ∪ N )∗ such that γ ⇒∗ ηατ ⇒ ηβτ ⇒∗ x.
Where a generative grammar is a device dened by a tuple < Σ, N, P, I > whereΣ is the alphabet of the language, N is a set of variables usually called nonterminals, P ⊂ (N ∪ Σ)∗ × (N ∪ Σ)∗ is the set of generative rules, I is the nite
set of axioms, which are elements of (Σ ∪ N )∗ . The language it represents is thestrings over Σ that can be derived from an element of I using the rules of P (⇒is the derivation relation, and ⇒∗ its symetric and transitive closure).
We conjecture that most algorithms whose characteristic sample is known
to be polynomial in the size of the target representation will also admit a characteristic sample polynomial in the size of the smallest structurally complete
set. This is the case for instance for the well-known RP N I algorithm [4] thatlearns regular languages from positive and negative examples. Moreover, somealgorithms whose characteristic sample are not polynomial in the size of thegrammar can admit a characteristic sample that is polynomial in the size of thesmallest structurally complete set. This is the case for instance of the algorithm
SGL that learns the substitutable context-free languages [1].

References
1. A. Clark and R. Eyraud. Polynomial identication in the limit of substitutable
context-free languages. Journal of Machine Learning Research, 8:17251745, 2007.
2. C. de la Higuera. Characteristic sets for polynomial grammatical inference. Machine
Learning Journal, 27:125138, 1997.
3. E. M. Gold. Language identication in the limit. Information and Control,
10(5):447474, 1967.
4. J. Oncina and P. García. Identifying regular languages in polynomial time. In
Advances in Structural and Syntactic Pattern Recognition, volume 5 of Series in
Machine Perception and Articial Intelligence, pages 99108. 1992.