We explore the descriptive power, in terms of syntactic phenomena, of a formalism that extends Tree-Adjoining Grammar (TAG) by adding a fourth level of hierarchical decomposition to the three levels TAG already employs.While extending the descriptive power minimally, the additional level of decomposition allows us to obtain a uniform account of a range of phenomena that has heretofore been difficult to encompass, an account that employs unitary elementary structures and eschews synchronized derivation operations, and which is, in many respects, closer to the spirit of the intuitions underlying TAG-based linguistic theory than previously considered extensions to TAG.

A natural next step in the evolution of constraint-based grammar formalisms from rewriting formalisms is to abstract fully away from the details of the grammar mechanism---to express syntactic theories purely in terms of the properties of the class of structures they license. By focusing on the structural properties of languages rather than on mechanisms for generating or checking structures that exhibit those properties, this model-theoretic approach can offer simpler and significantly clearer expression of theories and can potentially provide a uniform formalization, allowing disparate theories to be compared on the basis of those properties. We discuss L2K, P, a monadic second-order logical framework for such an approach to syntax that has the distinctive virtue of being superficially expressive---supporting direct statement of most linguistically significant syntactic properties---but having well-defined strong generative capacity---languages are definable in L2K, P iff they are strongly context-free. We draw examples from the realms of GPSG and GB.

We define a decidable class of TAGs that is strongly equivalent to CFGs and is cubic-time parsable. This class serves to lexicalize CFGs in the same manner as the LCFGs of Schabes and Waters but with considerably less restriction on the form of the grammars. The class provides a normal form for TAGs that generate local sets in much the same way that regular grammars provide a normal form for CFGs that generate regular sets.

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.

In this paper we introduce a logic for describing trees which allows us to reason about both the parent and domination relationship. The use of domination has found a number of applications, such as in deterministic parsers based on Description theory (Marcus, Hindle & Fleck, 1983), in a compact organization of the basic structures of Tree-Adjoining Grammars (Vijay-Shanker & Schabes, 1992), and in a new characterization of the adjoining operation that allows a clean integration of TAGs into the unification-based framework (Vijay-Shanker, 1992) Our logic serves to formalize the reasoning on which these applications are based.