BibTeX

@inProceedings{ljunglof-2004-grammatical-10786,
	title        = {Grammatical Framework and multiple context-free grammars},
	abstract     = {We show that there is a simple one-to-one correspondence between Grammatical Framework with context-free backbone and Multiple Context-Free Grammars (MCFG). Since the parsing complexity for MCFGs is known to be polynomial in the length of the input, we get the same result for context-free GF. },
	booktitle    = {FG-04, 9th Conference on Formal Grammar},
	author       = {Ljunglöf, Peter},
	year         = {2004},
}

@book{ljunglof-2004-expressivity-10794,
	title        = {Expressivity and Complexity of the Grammatical Framework},
	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.},
	author       = {Ljunglöf, Peter},
	year         = {2004},
	publisher    = {Chalmers University of Technology},
	address      = {Göteborg},
	ISBN         = {91-628-6331-2},
}

@article{ljunglof-2004-functional-10780,
	title        = {Functional chart parsing of context-free grammars},
	abstract     = {This paper implements a simple and elegant version of bottom-up Kilbury chart parsing
(Kilbury, 1985; Wir´en, 1992). This is one of the many chart parsing variants, which are
all based on the data structure of charts. The chart parsing process uses inference rules to
add new edges to the chart, and parsing is complete when no further edges can be added.
One novel aspect of this implementation is that it doesn’t have to rely on a global
state for the implementation of the chart. This makes the code clean, elegant and declarative,
while still having the same space and time complexity as the standard imperative
implementations.},
	journal      = {Journal of Functional Programming},
	author       = {Ljunglöf, Peter},
	year         = {2004},
	volume       = {14},
	number       = {6},
	pages        = {669--680},
}