Studies in the Logic of Trees
	       with Applications to Grammar Formalisms
			     James Rogers
		       Advisor K. Vijay-Shanker

This dissertation presents a series of studies in which we employ the
machinery of mathematical logic in exploring the formal properties of
trees.  While our results are diverse, they are connected by a common
core logical language and by the fact that they address issues related
to the precise meaning of descriptions of trees and of sets of trees
that arise in formal grammars of natural language.  Such descriptions
are typically employed by formalisms that express grammars as
constraints on the structure of the sentences in the language rather
than as rewriting rules.

Our initial study is an exploration of {\em quasi-trees}---partial
descriptions of trees, arising in recent research in Tree-Adjoining
Grammars, that describe the set of all trees derivable from a given
initial tree by the adjunction operation.  We formalize the notions of
partial descriptions of trees and of quasi-trees in the
quantifier-free fragment of our language.  Using these notions we
provide mechanisms that resolve arbitrary descriptions into equivalent
sets of quasi-trees and that construct minimal models of those
quasi-trees.  These mechanisms serve to decide if such a description
is satisfiable and, if it is, to produce the linguistically
appropriate representatives of the trees that it describes.

We then turn to the monadic second-order variant of our language
($L^2_{K,P}$), and show that it is equivalent in expressive power to
the language of {\em SnS}---the monadic second-order theory of
multiple successor functions.  This gives us a descriptive complexity
result for the {\em local sets}: a set of finite trees is local (is a
set of derivation trees generated by some context-free grammar) iff it
is definable in $L^2_{K,P}$.  As this language is capable of
expressing naturally many of the kinds of constraints on the structure
of trees that occur in modern grammar formalisms, this result provides
a powerful tool for determining the complexity of languages defined in
these formalisms relative to those definable by context-free grammars.
The final two studies are applications of this result.

In the first of these applications we explore definability and
non-definability of the principles of {\em Government and Binding
Theory}.  We get results of both types.  We show that {\em
free-indexation}, as it is usually employed in GB, is not definable in
$L^2_{K,P}$, and therefore not enforceable by CFGs.  Furthermore, we
show that even in an extremely weak form free-indexation is capable of
defining theories for which it is impossible to determine consistency,
and thus, may be inappropriate for any account of natural language.
We go on to show, however, that a set of GB principles capable of
describing substantially all of English syntax is definable in
$L^2_{K,P}$.  This establishes that the language licensed by this
theory within the GB framework is strongly context-free.  This gives
an indication of the strength of this technique, since prior to this
it has been difficult to show that such languages are even recursive.

Finally, we use definability in $L^2_{K,P}$ in identifying a decidable
class of Tree-Adjoining Grammars that is strongly context-free.  This
provides a normal form for TAGs that generate local sets in much the
same way that Regular Grammars are a normal form for CFGs that
generate regular languages.  We show, further, that the string
languages of TAGs in this class can be recognized in cubic time, and
that the class serves to lexicalize CFGs in a way that is potentially
more flexible than previous means.