摘要：Abstract In the syntactic theory of Tesni`ere (1959) the structural description of sentences are given as graphs. We discuss how the graph-theoretic concept of path-width is relevant in this approach. In particular, we point out the importance of graphs with path-width 6 in connection with natural language processing, and give a short proof of the characterization theorem of trees with path-width k. 1 The linguistic background Following the pioneering work of Tesni`ere [Te], the field of dependency grammar evolved at a steady pace. For results and references, see [Ma] and [Me]. In the present note we concentrate on one particular dependency model, put forth by K'alm'an and Kornai [KK], although our observations are applicable for a wider range of dependency formalisms where the syntactic description of a sentence is given as an ordered graph (with vertices corresponding to words and arcs corresponding to dependencies). In this model a grammatical derivation starts with a dependency graph wh...

原文链接:http://www.ams.org/mathscinet-getitem?mr=1158774

送人玫瑰，手留余香~如您已下载到该资源，可在回帖当中上传与大家共享，欢迎来CDA社区交流学习。（仅供学术交流用。）