Computational feasibility of some constrained grammatical formalisms for natural language

Recent research in computational linguistics suggests that context free grammars (CFGs) are not powerful enough to express a variety of syntactic phenomena found in natural language. These constructions can be handled adequately by some newly developed grammatical formalisms like tree adjoining grammars (TAGs) and control grammars (CGs) which are strictly more powerful than CFGs. However, previous research in the area had largely focussed on linguistic issues without fully addressing computational concerns pertaining to efficient parsing of these formalisms. In this dissertation, we investigate the sequential and parallel complexity of the recognition problem for languages generated by TAGs and CGs. We demonstrate several algorithms, which establish the feasibility of the problem in both the sequential and parallel setting. Further, we study the comparative complexity of various levels of the control language hierarchy. Several results are obtained, among them the strict separability of the hierarchy and the non-recursive nature of the succinctness problem for the hierarchy