TAG Parsing as Model Enumeration

Ralph Debusmann, Denys Duchier, Marco Kuhlmann, and Stefan Thater. TAG Parsing as Model Enumeration. In Proceedings of the Seventh International Workshop on Tree Adjoining Grammars and Related Formalisms (TAG+), pages 148–154, Vancouver, Canada, 2004.


This paper introduces well-ordered derivation trees and makes use of this concept in a novel axiomatization of the TAG parsing problem as a constraint satisfaction problem. Contrary to prior approaches, our axiomatization focuses on the derivation trees rather than the derived trees. Well-ordered derivation trees are our primary models, whereas the derived trees serve solely to determine word order.