Our reduction to Datalog brings sophisticated techniques for Datalog query evaluation to the problems of parsing and generation, and establishes a tight bound on the computational complexity of recognition for a wide range of grammars.
it shows that the use of higher-order λ-terms for semantic representation need not be avoided for the purpose of achieving computational tractability.