Learnable Classes of General Combinatory Grammars

Erwan Moreau (1)

1 LINA - Laboratoire d'Informatique de Nantes Atlantique

Kanazawa has shown that k-valued classical categorial gram- mars have the property of finite elasticity [1], which is a sufficient condi- tion for learnability. He has also partially extended his result to general combinatory grammars, but left open the question of whether some sub- sets of general combinatory grammars have finite elasticity. We propose a new sufficient condition which implies learnability of some classes of k-valued general combinatory grammars, focusing on the way languages are expressed through a grammatical formalism rather than the classes of languages themselves.

Keywords: Grammatical inference; Categorial grammars; Gold's model

Domains: Document and Text Processing; Machine Learning [cs.LG]

Erwan Moreau. Learnable Classes of General Combinatory Grammars. 5th International Conference on Logical Aspects of Computational Linguistics, LACL 2005, Apr 2005, Bordeaux, France. pp.189--204. ⟨hal-00487064⟩