tailieunhanh - Báo cáo khoa học: "Dependency Parsing with an Extended Finite State Approach"

The book by Mel~uk (1988) presents a comprehensive exposition of dependency syntax. Computational approaches to dependency syntax have recently become quite popular (., a workshop dedicated to computational approaches to dependency grammars has been held at COLING/ACL'98 Conference). J~irvinen and Tapananinen have demonstrated an efficient wide-coverage dependency parser for English (Tapanainen and J~irvinen, 1997; J£rvinen and Tapanainen, 1998). The work of Sleator and Temperley(1991) on link grammar, an essentially lexicalized variant of dependency grammar, has also proved to be interesting in a number of aspects. . | Dependency Parsing with an Extended Finite state Approach Kemal Oflazer Department of Computer Engineering Bilkent University Ankara 06533 Turkey Abstract This paper presents a dependency parsing scheme using an extended finite state approach. The parser augments input representation with channels so that links representing syntactic dependency relations among words can be accommodated and iterates on the input a number of times to arrive at a fixed point. Intermediate configurations violating various constraints of projective dependency representations such as no crossing links no independent items except sentential head etc are filtered via finite state filters. We have applied the parser to dependency parsing of Turkish. 1 Introduction Recent advances in the development of sophisticated tools for building finite state systems . XRCE Finite State Tools Karttunen et al. 1996 AT T Tools Mohri et al. 1998 have fostered the development of quite complex finite state systems for natural language processing. In the last several years there have been a number of studies on developing finite state parsing systems Koskenniemi 1990 Koskenniemi et al. 1992 Grefenstette 1996 Ait-Mokhtar and Chanod 1997 . There have also been a number of approaches to natural language parsing using extended finite state approaches in which a finite state engine is applied multiple times to the input or various derivatives thereof until some stopping condition is reached. Roche 1997 presents an approach for parsing in which the input is iteratively bracketed using a finite state transducer. Abney 1996 presents a finite state parsing approach in which a tagged sentence is parsed by transducers which progressively transform the input to sequences of symbols representing phrasal constituents. This paper presents an approach to dependency parsing using an extended finite state model resembling the approaches of Roche and Abney. The parser produces outputs that encode a .