Paper: Parsing and Generation as Datalog Queries

ACL ID P07-1023
Title Parsing and Generation as Datalog Queries
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2007
Authors

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-...