  Since the early Sixties and Seventies it has been known that the regular and
context-free languages are characterized by definability in the monadic
second-order theory of certain structures. More recently, these descriptive
characterizations have been used to obtain complexity results for constraint-
and principle-based theories of syntax and to provide a uniform model-theoretic
framework for exploring the relationship between theories expressed in
disparate formal terms. These results have been limited, to an extent, by the
lack of descriptive characterizations of language classes beyond the
context-free. Recently, we have shown that tree-adjoining languages (in a
mildly generalized form) can be characterized by recognition by automata
operating on three-dimensional tree manifolds, a three-dimensional analog of
trees. In this paper, we exploit these automata-theoretic results to obtain a
characterization of the tree-adjoining languages by definability in the monadic
second-order theory of these three-dimensional tree manifolds. This not only
opens the way to extending the tools of model-theoretic syntax to the level of
TALs, but provides a highly flexible mechanism for defining TAGs in terms of
logical constraints.
  This is the full version of a paper to appear in the proceedings of
COLING-ACL'98 as a project note.
