Đang chuẩn bị liên kết để tải về tài liệu:
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@nii.ac.jp 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 .