Parsing and Generation as Datalog Queries

Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 176–183, Prague, Czech Republic, June 2007. c⃝2007 Association for Computational Linguistics 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 sur- face realization for grammar formalisms with “context-free” derivations, coupled with Mon- tague semantics (under a certain restriction) can be reduced in a uniform way to Datalog query evaluation. As well as giving a polynomial- time algorithm for computing all derivation trees (in the form of a shared forest) from an in- put string or input logical form, this reduction has the following complexity-theoretic conse- quences for all such formalisms: (i) the de- cision problem of recognizing grammaticality (surface realizability) of an input string (logical form) is in LOGCFL; and (ii) the search prob- lem of finding one logical form (surface string) from an input string (logical form) is in func- tional LOGCFL. Moreover, the generalized sup- plementary magic-sets rewriting of the Datalog program resulting from the reduction yields ef- ficient Earley-style algorithms for both parsing and generation. 1 Introduction The representation of context-free grammars (aug- mented with features) in terms of definite clause pro- grams 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). 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 representation of a CFG. By naive (or seminaive) bottom-up evaluation (see, e.g., Ullman, 1988), the answer to such a query can be computed in polynomial time in the size of the database for any Datalog program. By recording rule instances rather than derived facts, a packed rep- resentation of the complete set of Datalog derivation trees for a given query can also be obtained in poly- nomial time by the same technique. Since a Data- log derivation tree uniquely determines a grammar derivation tree, this gives a reduction of context-free recognition and parsing to query evaluation in Data- log. In this paper, we show that a similar reduction to Datalog is …

Content truncated to 500 words