Identification in the Limit of Some of Penn and Buzkowski's Classes is NP-hard

Christophe Costa-Florencio (Utrecht University)


In [Buskowski 1987] and [Buszkowski and Penn, 1990] some `discovery
procedures' for classical categorial grammars were defined.  These
procedures take a set of structures (strings labeled with derivational
information) as input and yield a set of hypotheses.  In [Kanazawa,
1990] learning functions based on these discovery procedures were
studied, and it was shown that some of the classes associated with
these functions can be identified in the limit (i.e. are learnable),
by a computable function.  The time complexity of these functions
however was still left an open question.  In will show that the
learning functions for these learnable classes are all NP-hard.