To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Expressivity and Complexi… - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

Expressivity and Complexity of the Grammatical Framework

Doctoral thesis
Authors Peter Ljunglöf
Date of public defense 2004-12-07
Opponent at public defense Dr Bernard Lang, INRIA Rocquencourt, France
ISBN 91-628-6331-2
Publisher Chalmers University of Technology
Place of publication Göteborg
Publication year 2004
Published at Department of Computer Science and Engineering (GU)
Language en
Links https://gup.ub.gu.se/file/207628
Keywords Grammatical Framework, generalized context-free grammar, multiple context-free grammar, context-free rewriting systems, type theory, expressive power, abstract syntax, linearization, parsing
Subject categories Language Technology (Computational Linguistics)

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.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?