Premium
OBTAINING TREES FROM THEIR DESCRIPTIONS: AN APPLICATION TO TREE‐ADJOINING GRAMMARS
Author(s) -
Rogers James,
VIJAYSHANKER K.
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00005.x
Subject(s) - tree (set theory) , computer science , l attributed grammar , tree adjoining grammar , adjunction , set (abstract data type) , rule based machine translation , mathematics , theoretical computer science , context free grammar , combinatorics , artificial intelligence , programming language , pure mathematics
Partial descriptions are sets of constraints which do not necessarily determine a unique object. Two related issues arise when objects arc specified by partial descriptions. The first asks whether a given partial description is satisfied by any object. The second seeks to produce, from a satisfiable description, an appropriate representative of those objects which satisfy it (where the notion of appropriate is defined by the circumstances in which the partial descriptions are employed). We explore these issues in the context of two recent proposals utilizing partial descriptions of trees in the area of tree‐adjoining grammars. One involves the use of descriptions of trees in reinterpreting TAGs as a constraint‐based formalism. In the other these descriptions are the basis of a compact representation of lexicalized TAG 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. A partial description for which there is a unique such minimal tree will be called a quasi‐tree. Our work provides precise foundations for the use of descriptions of trees in these proposals. We formalize the notions of partial descriptions of trees and of quasi‐trees, and using this, provide a mechanism which derives, from an arbitrary description, an equivalent set of quasi‐trees. The description is satisfiable iff that set of quasi‐trees is nonempty. We then provide a second mechanism which constructs the unique minimal trees satisfying these quasi‐trees. Thus these mechanisms decide our issues in a strong way–they resolve any description into an equivalent set of descriptions which have unambiguous representative trees, and produce, from that set of descriptions, those representative trees. Such mechanisms are presupposed by the LTAG proposal, but are provided in a complete form for the first time here.