This thesis investigates the expressive power and parsing complexity of the Grammatical Framework (GF), a formalism originally designed for displaying formal propositions and proofs in natural language. This is done by relating GF with two more well-known grammar formalisms; Generalized Context-Free Grammar (GCFG), best seen as a framework for describing various grammar formalisms; and Parallel Multiple Context-Free Grammar (PMCFG), an instance of GCFG.Since GF is a fairly new theory, some questions about expressivity and parsing complexity have until now not been answered; and these questions are the mainfocus of this thesis. The main result is that the important subclass context-free GF is equivalent to PMCFG, which has polynomial parsing complexity, and whose expressive power is fairly well known.Furthermore, we give a number of tabular parsing algorithms for PMCFG with polynomial complexity, by extending existing algorithms for context-free grammars. We suggest three possible extensions of GF/PMCFG, and discuss how theexpressive power and parsing complexity are influenced. Finally, we discuss the parsing problem for unrestricted GF grammars, which is undecidable in general.We nevertheless describe a procedure for parsing grammars containing higher-order functions and dependent types. http://hdl.handle.net/2077/16377

@book{Ljungl?f,Peter2004-32,
	title		= "Expressivity and Complexity of the Grammatical Framework",
	author		= "Ljunglöf, Peter",
	year		= "2004",
	publisher	= "Chalmers University of Technology",
	address		= "Göteborg",
	isbn		= "91-628-6331-2",
	url		= "http://hdl.handle.net/2077/16377",
}