Computation and Linguistic Theory: A Government Binding Theory Parser Using Tree Adjoning Grammar

Government Binding (GB) theory, as a competence theory of grammar, is intended to define what a speaker's knowledge of language consists of. The theory proposes a system of innate principles and constraints which determine the class of possible languages and, once instantiated by the parameter values for a given language, the class of well-formed sentences of that language [Chomsky, 1981]. In this thesis, I address the problem of how this knowledge of language is put to use. The answer I give to this question takes the shape of an implemented computational model, a parser, which utilizes the formulation of knowledge of language as proposed in GB theory. GB as a theory of grammar poses a particular problem for instantiation within a cognitively feasible computational model. It has a rich deductive structure whose obvious direct implementation as a set of axioms in a first order theorem prover runs up against the problem of undecidability. Thus, if we accept GB theory as psychologically real, and thus as functioning causally with respect to linguistic processing, there seems to be a paradox: we need a way of putting our knowledge of language, represented in GB theory, to use in a processing theory in an efficient manner. I will suggest a way out of this paradox. I propose to constrain the class of possible grammatical principles by requiring them to be statable over a linguistically and mathematically motivated domain, that of a tre