TAILIEUCHUNG - Báo cáo khoa học: "A Polynomial-Time Parsing Algorithm for TT-MCTAG"

This paper investigates the class of TreeTuple MCTAG with Shared Nodes, TTMCTAG for short, an extension of Tree Adjoining Grammars that has been proposed for natural language processing, in particular for dealing with discontinuities and word order variation in languages such as German. It has been shown that the universal recognition problem for this formalism is NP-hard, but so far it was not known whether the class of languages generated by TT-MCTAG is included in PTIME. We provide a positive answer to this question, using a new characterization of TTMCTAG. . | A Polynomial-Time Parsing Algorithm for TT-MCTAG Laura Kallmeyer Collaborative Research Center 441 Universitat Tubingen Tubingen Germany lk@ Giorgio Satta Department of Information Engineering University of Padua Padova Italy satta@ Abstract This paper investigates the class of TreeTuple MCTAG with Shared Nodes TT-MCTAG for short an extension of Tree Adjoining Grammars that has been proposed for natural language processing in particular for dealing with discontinuities and word order variation in languages such as German. It has been shown that the universal recognition problem for this formalism is NP-hard but so far it was not known whether the class of languages generated by TT-MCTAG is included in PTIME. We provide a positive answer to this question using a new characterization of TT-MCTAG. 1 Introduction For a large range of linguistic phenomena extensions of Tree Adjoining Grammars Joshi et al. 1975 or TAG for short have been proposed based on the idea of separating the contribution of a lexical item into several components. Instead of single trees these grammars contain multi- sets of trees. Examples are tree-local and set-local multicomponent TAG Joshi 1985 Weir 1988 MC-TAG for short non-local MCTAG with dominance links Becker et al. 1991 Vector-TAG with dominance links Rambow 1994 and more recently Tree-Tuple MCTAG with Shared Nodes Lichte 2007 or TT-MCTAG for short. For some of the above formalisms the word recognition problem is NP-hard. This has been shown for non-local MCTAG Rambow and Satta 1992 even in the lexicalized case Champollion 2007 . Some others generate only polynomial languages but their generative capacity is too limited to deal with all natural language phenomena. This has been argued for tree-local and even set-local MCTAG on the basis of scrambling data from lan guages such as German Becker et al. 1992 Rambow 1994 . In this paper we focus on TT-MCTAG Lichte 2007 . So far it has been shown that the .

• Báo cáo khoa học
• A Polynomial Time Parsing Algorithm
• TT MCTAG
• Laura Kallmeyer
• báo cáo khoa học
• báo cáo ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân tích ngữ nghĩa
• Phân loại tin tự động
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Tách từ tiếng Việt
• Gán nhãn từ loại
• Phân tích cú pháp
• Nghĩa từ vựng
• Phân giải nhập nhằng từ
• Phân loại văn bản
• Lexical chain
• Phản hồi thông tin
• Bài toán PTCP
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học