On learning discontinuous dependencies from positive data

Denis Béchet (1) , Alexandre Dikovsky (1) , Annie Foret (2) , Erwan Moreau (1)

1 LINA - Laboratoire d'Informatique de Nantes Atlantique
2 LIS - Logical Information Systems

This paper is concerned with learning in the model of Gold the Categorial Dependency Grammars (CDG), which express discontin- uous (non-projective) dependencies. We show that rigid and k-valued CDG (without optional and iterative types) are learnable from strings. In fact, we prove that the languages of dependency nets coding rigid CDGs have finite elasticity, and we show a learning algorithm. As a standard corollary, this result leads to the learnability of rigid or k- valued CDGs (without optional and iterative types) from strings.

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

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

Denis Béchet, Alexandre Dikovsky, Annie Foret, Erwan Moreau. On learning discontinuous dependencies from positive data. 9th conference on Formal Grammar (FG 2004), Aug 2004, Nancy, France. pp.1--16. ⟨hal-00487058⟩