Contextual Grammars and Dependency Trees

TALN 2003, Batz-sur-Mer, 11–14 juin 2003 Contextual Grammars and Dependency Trees � Radu Gramatovici (1), Carlos Mart´ın-Vide (2) (1) Faculty of Mathematics and Computer Science, University of Bucharest Academiei 14, 70109, Bucharest, Romania Email: radu@funinf.cs.unibuc.ro (2) Research Group on Mathematical Linguistics, Rovira i Virgili University Pl. Imperial T`arraco 1, 43005 Tarragona, Spain Email: cmv@astor.urv.es Mots-clefs – Keywords Grammaire contextuelle, arbre de dependance, arbre projectif de d´ependance Contextual grammar, dependency tree, projective dependency tree R´esum´e - Abstract On pr´esente une nouvelle variante de grammaire contextuelle structur´ee, qui produit des arbres de d´ependance. Le nouveau mod`ele g´en´eratif, appel´e grammaire contextuelle de d´ependance, am´eliore la puissance g´en´erative forte et faible des grammaires contextuelles, tout en ´etant un candidat potentiel pour la description math´ematique des mod´eles syntactiques de d´ependance. A new variant of structured contextual grammar, which generates dependency trees, is intro- duced. The new generative model, called dependency contextual grammar, improves both the strong and weak generative power of contextual grammars, while being a potential candidate for the mathematical description of dependency-based syntactic models. �This work was written during a research visit of the first author at the Research Group on Mathematical Linguistics of Rovira i Virgili University. The research visit was funded by the NATO Scientific Committee. R. Gramatovici, C. Mart´ın-Vide 1 Introduction Contextual grammars were introduced in 1969 by Solomon Marcus (Marcus, 1969) as an at- tempt to transform in generative devices some procedures developed within the framework of analytical models (see (Marcus, 1997) for a comprehensive discussion on the linguistic mo- tivations of contextual grammars). In many respects, (the mathematical model of) contextual grammars and (the linguistic model of) dependency grammars ((Mel’ˇcuk, 1987) and others) have the same roots. The similitude between contextual grammars and dependency syntactic models based on dependency trees go further, since both formalisms deal mostly with symbols of the language and less or at all with auxiliary symbols as in the case of formalisms based on constituents trees. A similar argument to this one is presented in (Mr´az et al., 2000), where contextual mechanism is described as dual to the analysis by reduction linguistic method. However, no relationship was established yet between contextual and dependency grammars. This happened probably because, originally, contextual grammars developed a string generative mechanism and structures on strings generated by contextual grammars were introduced only recently in (Mart´ın-Vide & P˘aun, 1998). In this paper, we propose a new approach to the generation of dependency trees (D-trees), based on contextual grammars. The notion of internal dependency contextual grammar (DCG) is introduced, by adding dependency descriptions to contextual rules from ordinary contextual grammars. In a DCG, the derivation relation is constrained in two ways: contexts are selected by (strings of) words, but also by the correct construction of the D-tree. Simplifying, string insertion rules stand for the word order, while dependencies express mainly the dominance relationship between words, as in unordered syntactic D-trees. Local and long distance depen- dencies are treated in an uniform way, using the smooth contextual mechanism. Several formal examples are …

Content truncated to 500 words