CSLI Publications logo
new books
knuth books
for authors
CSLI Publications
Facebook CSLI Publications RSS feed
CSLI Publications Newsletter Signup Button
Learnable Classes of Categorial Grammars cover

Learnable Classes of Categorial Grammars

Makoto Kanazawa

This book investigates learnability of various classes of classical categorial grammars within the Gold paradigm of identification in the limit from positive data. Two types of learning, learning from structures and learning from flat strings, are considered. The class of k-valued grammars, for k = 1,2,3,…, is shown to be learnable both from structures and from strings, while the class of least-valued grammars and the class of least-cardinality grammars are shown to be learnable from structures. In proving these learnable results, crucial use is made of a theorem on the concept known as finite elasticity. The learning algorithms used in this work build on Buszkowski and Penn's algorithm for finding categorial grammars from input consisting of functor-argument structures.

Makoto Kanazawa is Associate Professor in the Department of Cognitive and Information Sciences, Chiba University.


  • Preface
  • 1 Introduction
  • 2 Learnability Theory
    • 2.1 Basic Definitions
    • 2.2 Structural Conditions and (Un)learnability
    • 2.3 Constraints on Learning Functions
    • 2.4 Representative Results
  • 3 A Theorem on Finite Elasticity
  • 4 Classical Categorical Grammar
    • 4.1 Basic Definitions
    • 4.2 Basic Facts about Classical Categorial Grammars
    • 4.3 Substitutions and Standardizations
  • 5 Basic Theory of Rigid Grammar
    • 5.1 Rigid and k-Valued Grammars
    • 5.2 Characteristics Samples for Rigid Grammars
    • 5.3 The Lattice of Rigid Grammars
    • 5.4 The Rigid Structure Languages
  • 6 Learning from Structure I: Rigid, k-Valued, and Least-Valued Grammars
    • 6.1 Rigid Grammas
    • 6.2 k-Valued Grammars
    • 6.3 Least-Valued Grammars
  • 7 Learnign from Structures II: Subclasses of the Optimatl Grammars
    • 7.1 Optimal Grammars
    • 7.2 Least Cardinality Grammars
    • 7.3 Minmal Grammars
    • 7.4 Summary on Learning from Structures
  • 8 Learning from Strings
    • 8.1 k-Valued Grammars
    • 8.2 Other Classes
  • 9 Variations
    • 9.1 General Combinatory Grammars
    • 9.2 Montague Grammars
  • 10 Conclusion
  • A Implementations in Prolog
  • Bibliography
  • List of Notation
  • Name Index
  • Subject Index


ISBN (Paperback): 1575860961 (9781575860961)
ISBN (Cloth): 157586097X (9781575860978)
ISBN (Electronic): 1575869969 (9781575869964)

Subject: Linguistics; Categorical Grammar; Learning Ability

Add to Cart
View Cart

Check Out

Distributed by the
University of
Chicago Press

pubs @ csli.stanford.edu