TAILIEUCHUNG - Báo cáo khoa học: "Parsing and Generation as Datalog Queries"

We show that the problems of parsing and surface realization for grammar formalisms with “context-free” derivations, coupled with Montague semantics (under a certain restriction) can be reduced in a uniform way to Datalog query evaluation. As well as giving a polynomialtime algorithm for computing all derivation trees (in the form of a shared forest) from an input string or input logical form, this reduction has the following complexity-theoretic consequences for all such formalisms: (i) the decision problem of recognizing grammaticality (surface realizability) of an input string (logical form) is in LOGCFL; and (ii) the search problem of finding one. | Parsing and Generation as Datalog Queries Makoto Kanazawa National Institute of Informatics 2-1-2 Hitotsubashi Chiyoda-ku Tokyo 101-8430 Japan kanazawa@ Abstract We show that the problems of parsing and surface realization for grammar formalisms with context-free derivations coupled with Montague semantics under a certain restriction can be reduced in a uniform way to Datalog query evaluation. As well as giving a polynomialtime algorithm for computing all derivation trees in the form of a shared forest from an input string or input logical form this reduction has the following complexity-theoretic consequences for all such formalisms i the decision problem of recognizing grammaticality surface realizability of an input string logical form is in LOGCFL and ii the search problem of finding one logical form surface string from an input string logical form is in functional LOGCFL. Moreover the generalized supplementary magic-sets rewriting of the Datalog program resulting from the reduction yields efficient Earley-style algorithms for both parsing and generation. 1 Introduction The representation of context-free grammars augmented with features in terms of definite clause programs is well-known. In the case of a bare-bone CFG the corresponding program is in the function-free subset of logic programming known as Dat-alog. For example determining whether a string John found a unicorn belongs to the language of the CFG in Figure 1 is equivalent to deciding whether the Datalog program in Figure 2 together with the database in 1 can derive the query - S 0 4 . 1 John 0 1 . found 1 2 . a 2 3 . unicorn 3 4 . 176 S NP VP VP V NP V V Conj V NP Det N NP John V found V caught Conj and Det a N unicorn Figure 1 A CFG. S i j - NP i k VP k j . VP i j - V i k NP k j . V i j - V i k Conj k l V l j . NP i j - Det i k N k j . NP i j - John i j . V i j - found i j . V i j - caught i j . Conj i j - and i j . Det i j - a i j . N i j - unicorn i j . Figure 2 The Datalog .

• Báo cáo khoa học
• Parsing and Generation
• Datalog Queries
• Makoto Kanazawa
• báo cáo khoa học
• mô hình ngôn ngữ
• xử lý ngôn ngữ tự nhiên
• Sentence Diagram Generation
• Dependency Parsing Elijah Mayfield Division
• Science and Mathematics
• báo cáo ngôn ngữ
• Generation as Dependency Parsing
• Alexander Koller
• Kristina Striegnitz
• Compiler Construction
• Context free languages
• Table driven top down parsing
• The programming language Oberon 0
• Straight code generation
• Delayed code generation
• 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 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