Publication details

Saarland University Computer Science

Well-Nested Drawings as Models of Syntactic Structure (Extended Version)

Manuel Bodirsky, Marco Kuhlmann, Mathias Möhl

Technical Report, 2005

This paper investigates drawings (totally ordered forests) as models of syntactic structure. It offers a new model-based perspective on lexicalised Tree Adjoining Grammar by characterising a class of drawings structurally equivalent to TAG derivations. The drawings in this class are distinguished by a restricted form of non-pro jectivity (gap degree at most one) and the absence of interleaving substructures (well-nestedness). We demonstrate that well-nested drawings allow for efficient processing by defining a simple constraint language for them and presenting an algorithm that decides in polynomial time whether a formula in that constraint language is satisfiable on a well-nested drawing.

This paper is the extended version of an article that appears in the proceedings of the 10th Conference on Formal Grammar and the 9th Meeting on Mathematics of Language, Edinburgh, Scotland, UK, 2005

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009