Studies in the logic of trees with applications to grammar formalisms
James Rogers · 1994
We present a series of studies in which we employ the machinery of mathematical logic in exploring the formal properties of trees. These 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. Our initial study is an exploration of quasi-trees--partial descriptions of trees arising in recent research in Tree-Adjoining Grammars. We formalize the notion of quasi-trees in the quantifier-free fragment of our language. On this foundation, we develop mechanisms that decide if such a description is satisfiable and, if it is, to produce the linguistically appropriate representatives of the trees that it describes. Such mechanisms are presupposed by the TAG applications that employ quasi-trees. We then turn to the monadic second-order variant of our language ($L\sbsp{K,P}{2}$), and show that it is equivalent in expressive power to the language of SnS--the monadic second-order theory of multiple successor functions. This gives us a descriptive complexity result for the recognizable sets: a set of finite trees is recognizable (a projection of a set of derivation trees generated by some context-free grammar) iff it is definable in $L\sbsp{K,P}{2}$. The final two studies apply this result. First, we explore definability of the principles of Government and Binding Theory. We show that free-indexation, as it is usually employed in GB, is not definable in $L\sbsp{K,P}{2}$, and therefore not enforceable by CFGs. We go on to show, however, that the language licensed by a set of principles describing substantially all of English syntax is definable in $L\sbsp{K,P}{2}$, and thus 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\sbsp{K,P}{2}$ in identifying a decidable class of Tree-Adjoining Grammars that is strongly context-free. This class provides a normal form for TAGs that generate local sets and serves to lexicalize CFGs in a way that is more flexible than previous means.