Denis Bechet¹ and Annie Foret², ¹Nantes University, France, ²Univ. Rennes and IRISA, France

We consider the family of Categorial Dependency Grammars (CDG), as computational grammars for language processing. CDG are a class of categorial grammars defining dependency structures. They can be viewed as a formal system, where types are attached to words, combining the classical categorial grammars' elimination rules with valency pairing rules that are able to define non-projective (discontinuous) dependencies. Whereas the closure problem under iteration is open for the original version of CDG, we define "CDG extended with barriers" as an extended version of the original CDG that solves this formal issue. We provide a rule system and show that the extended version defines an Abstract Family of Languages (AFL) while preserving advantages of the original CDG in terms of expressivity, parsing and efficiency.

Logical approach to natural language, Type calculus, Categorial Grammar, Dependency Grammar, Abstract Family of Languages