We present an implemented compilation algorithm that translates HPSG into lexicalized feature-based TAG, relating concepts of the two theories. While HPSG has a more elaborated principle-based theory of possible phrase structures, TAG provides the means to represent lexicalized structures more explicitly. Our objectives are met by giving clear definitions that determine the projection of structures from the lexicon, and identify "maximal" projections, auxiliary trees and foot nodes.

A grammatical description often applies to a linguistic object only when that object has certain features. Such conditional descriptions can be indirectly modeled in Kay's Functional Unification Grammar (FUG) using functional descriptions that are embedded within disjunctive alternatives. An extension to FUG is proposed that allows for a direct representation of conditional descriptions. This extension has been used to model the input conditions on the systems of systemic grammar. Conditional descriptions are formally defined in terms of logical implication and negation. This formal definition enables the use of conditional descriptions as a general notational extension to any of the unification-based grammar representation systems currently used in computational linguistics.

Although disjunction has been used in several unification-based grammar formalisms, existing methods of unification have been unsatisfactory for descriptions containing large quantities of disjunction, because they require exponential time. This paper describes a method of unification by successive approximation, resulting in better average performance.

Unification-based grammar formalisms use structures containing sets of features to describe linguistic objects. Although computational algorithms for unification of feature structures have been worked out in experimental research, these algorithms become quite complicated, and a more precise description of feature structures is desirable. We have developed a model in which descriptions of feature structures can be regarded as logical formulas, and interpreted by sets of directed graphs which satisfy them. These graphs are, in fact, transition graphs for a special type of deterministic finite automation.This semantics for feature structures extends the ideas of Pereira and Shieber [11], by providing an interpretation for values which are specified by disjunctions and path values embedded within disjunctions. Our interpretation differs from that of Pereira and Shieber by using a logical model in place of a denotational semantics. This logical model yields a calculus of equivalences, which can be used to simplify formulas.Unification is attractive, because of its generality, but it is often computationally inefficient. Our model allows a careful examination of the computational complexity of unification. We have shown that the consistency problem for formulas with disjunctive values is NP-complete. To deal with this complexity, we describe how disjunctive values can be specified in a way which delays expansion to disjunctive normal form.