Logical embedded push‐down automata in tree‐adjoining grammar parsing

This paper extends the “parsing as deduction” approach to tree‐adjoining grammars by showing how a TAG recognition problem can be reduced to a Datalog deduction problem, and presents an SLD selection rule that makes the proof search correspond to a top‐down parse using the original grammar. Just as in the DCG extension of context‐free grammars, this approach permits nodes to be labeled with firsl‐order terms (rather than only atomic symbols). Finally the paper discusses implementation matters, and describes how the control rule can be efficiently implemented in Prolog.