Grammars for Local and Long Dependencies

Grammars for Local and Long Dependencies. Alexander Dikovsky Universit´e de Nantes, IRIN, 2, rue de la Houssini`ere BP 92208 F 44322 Nantes cedex 3 France Alexandre.Dikovsky@irin.univ-nantes.fr Abstract Polarized dependency (PD-) grammars are proposed as a means of efficient treatment of discontinuous construc- tions. PD-grammars describe two kinds of dependencies : local, explicitly de- rived by the rules, and long, implicitly specified by negative and positive va- lencies of words. If in a PD-grammar the number of non-saturated valencies in derived structures is bounded by a constant, then it is weakly equivalent to a cf-grammar and has a ����� - time parsing algorithm. It happens that such bounded PD-grammars are strong enough to express such phenomena as unbounded raising, extraction and ex- traposition. 1 Introduction Syntactic theories based on the concept of depen- dency have a long tradition. Tesni`ere (Tesni`ere, 1959) was the first who systematically described the sentence structure in terms of binary relations between words (dependencies), which form a de- pendency tree (D-tree for short). D-tree itself does not presume a linear order on words. How- ever, any its surface realization projects some lin- ear order relation (called also precedence). Some properties of surface syntactic structure can be ex- pressed only in terms of both dependency (or its transitive closure called dominance) and prece- dence. One of such properties, projectivity, re- quires that any word occurring between a word � and a word dependent on � be dominated by � In first dependency grammars (Gaifman, 1961) and in some more recent proposals: link gram- mars (Sleator and Temperly, 1993), projective dependency grammars (Lombardo and Lesmo, 1996) the projectivity is implied by definition. In some other theories, e.g. in word grammar (Hud- son, 1984), it is used as one of the axioms defin- ing acceptable surface structures. In presence of this property, D-trees are in a sense equiva- lent to phrase structures with head selection 1. It is for this reason that D-trees determined by grammars of Robinson (Robinson, 1970), cate- gorial grammars (Bar-Hillel et al., 1960), classi- cal Lambek calculus (Lambek, 1958), and some other formalisms are projective. Projectivity af- fects the complexity of parsing : as a rule, it al- lows dynamic programming technics which lead to polynomial time algorithms (cf. � �� � � -time algorithm for link grammars in (Sleator and Tem- perly, 1993)). Meanwhile, the projectivity is not the norm in natural languages. For example, in most European languages there are such regu- lar non-projective constructions as WH- or rel- ative clause extraction, topicalization, compara- tive constructions, and some constructions spe- cific to a language, e.g. French pronominal cli- tics or left dislocation. In terms of phrase struc- ture, non-projectivity corresponds to discontinu- ity. In this form it is in the center of dis- cussions till 70-ies. There are various depen- dency based approaches to this problem. In the framework of Meaning-Text Theory (Mel’ˇcuk and Pertsov, 1987), dependencies between (some- 1See (Dikovsky and Modina, 2000) for more details. times non adjacent) words are determined in …

Content truncated to 500 words