Obtaining Trees from Their Descriptions:
                 An Application to Tree-Adjoining Grammars
                                James Rogers
                              K. Vijay-Shanker

                                  ABSTRACT

Partial descriptions are sets of constraints which do not necessarily
determine a unique object.  Two related issues arise when objects are
specified by partial descriptions.  The first asks whether a given
description is satisfied by any object.  The second seeks to produce, from a
description, an appropriate representative of those objects which satisfy
it.  We explore these issues in the context of two recent proposals
utilizing partial descriptions of trees in the area of Tree-Adjoining
Grammars.  In this context, what counts as an appropriate representative of
the set of trees which satisfy a description is a tree in that set which is
minimal in the sense that every other tree in the set can be derived from it
by adjunction.  We call a partial description for which there is a unique
such minimal tree a quasi-tree.

We formalize the notions of partial descriptions of trees and of
quasi-trees, and, using these, provide mechanisms which resolve any
description of trees into an equivalent set of quasi-trees and which
produce, from that set, the minimal trees satisfying the description.  Such
mechanisms are presupposed by the proposals we consider, but are provided in
a complete form for the first time here.

Keywords: partial descriptions, tree-adjoining grammars, constraint-based
formalisms, tableau methods.