### Skapa referens, olika format (klipp och klistra)

**Harvard**

Ljunglöf, P. (2004) *Expressivity and Complexity of the Grammatical Framework*. Göteborg : Chalmers University of Technology (Technical report D - School of Computer Science and Engineering, Chalmers University of Technology, nr: 31 D).

** BibTeX **

@book{

Ljunglöf2004,

author={Ljunglöf, Peter},

title={Expressivity and Complexity of the Grammatical Framework},

isbn={91-628-6331-2},

abstract={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 main
focus 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 the
expressive 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.},

publisher={Institutionen för datavetenskap, Språkteknologi, Chalmers tekniska högskola,},

place={Göteborg},

year={2004},

series={Technical report D - School of Computer Science and Engineering, Chalmers University of Technology, no: 31 D},

keywords={Grammatical Framework, generalized context-free grammar, multiple context-free grammar, context-free rewriting systems, type theory, expressive power, abstract syntax, linearization, parsing},

note={172 pages},

}

** RefWorks **

RT Dissertation/Thesis

SR Electronic

ID 10794

A1 Ljunglöf, Peter

T1 Expressivity and Complexity of the Grammatical Framework

YR 2004

SN 91-628-6331-2

AB 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 main
focus 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 the
expressive 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.

PB Institutionen för datavetenskap, Språkteknologi, Chalmers tekniska högskola,

T3 Technical report D - School of Computer Science and Engineering, Chalmers University of Technology, no: 31 D

LA eng

LK http://hdl.handle.net/2077/16377

OL 30