The focus of this monograph is on learning categorial grammars from sequences of positive examples presented in the form of functor-argument structures. Sakakibara [1] has demonstrated that the class of reversible context-free grammars (CFGs) can be learned, in the limit, from positive examples in the form of unlabeled derivation trees of a particular form. Since the languages generated by the classical categorial grammars are exactly the same as those generated by the reversible CFGs (namely, the epsilon-free context-free languages), Kanazawa’s contribution lies in analyzing and comparing how well these learnability results transfer under a change in representation of the examples and in the classes of grammars that are permitted as hypotheses.

The results of the comparison are nontrivial. For instance, Sakakibara’s reversible context-free grammars can describe all context-free languages, but the learnable classes investigated by Kanazawa cannot. (Discovery of a normal-form learnable class of categorial grammars is still an open problem.) The author constructs algorithms that learn in the limit, from structural examples, the classes of k-valued, least-valued, and least-cardinality categorial grammars, all of which are extensions of the learnable class of rigid grammars (grammars in which each terminal symbol is assigned at most a single type). The k-valued grammars are shown to be learnable even from string examples. Several informative negative learning results are also presented (for instance, non-learnability of so-called “optimal grammars” from structural examples).

The book does an excellent job of summarizing previous work and preparing the reader for the main results. Someone with no more than a background in formal languages and computability theory should be able to follow the arguments and appreciate their significance. In addition, chapter 3 contains a generalization of Wright’s theorem on the closure under union of language classes with finite elasticity, which should prove useful in investigating other learnable classes of grammars and languages.

The text is clean, the presentation is clear and rigorous, and the comprehensive list of references will be helpful to anyone wishing to pursue some of the interesting open questions raised in this monograph.