Learnable Classes of Categorial Grammars
Makoto Kanazawa

Abstract:
This dissertation investigates learnability of various classes of
classical categorial grammars within the Gold paradigm of identification
in  the limit from positive data. Both learning from functor-argument
structures and learning from flat strings are considered.
The class of rigid grammars, the class of $k$-valued grammars 
($k$ = 2,3, ...), the class of least-valued grammars, and the class
of least-cardinality grammars are shown to be learnable from strings.
An interesting class that is not learnable even from structures is
treated as well. In proving learnability  results, Kanazawa makes
essential use of the concept known as finite elasticity, which is
a property of language classes. He proves that finite elasticity
is preserved under the inverse image of a finite-valued relation,
extending results of Wright's and of Moriyama and Sato's. Kanazawa
uses this theorem to `transfer' finite elasticity from the class
of rigid structure languages to the class of $k$-valued structure
languages, and then to the class of $k$-valued string languages. The
learning algorithms used incorporate Buszkowski and Penn's
algorithms for determining categorial grammars from input 
consisting of functor-argument structures.  Some of the learnability
results are extended to such loosely `categorial' formalisms as
combinatory grammar and Montague grammar. The appendix presents
Prolog implementations of some of the learning algorithms used
in this dissertation.