Skip to main content

BibTeX

@inProceedings{ljunglof-2005-polynomial-10789,
	title        = {A polynomial time extension of parallel multiple context-free grammar},
	abstract     = {It is already known that parallel multiple context-free grammar
(PMCFG) [1] is an instance of the equivalent formalisms simple literal
movement grammar (sLMG) [2, 3] and range concatenation grammar
(RCG) [4, 5]. In this paper we show that by adding the single operation of
intersection, borrowed from conjunctive grammar [6], PMCFG becomes
equivalent to sLMG and RCG. As a corollary we get that PMCFG with
intersection describe exactly the class of languages recognizable in polynomial
time.},
	booktitle    = {LACL-05, 5th Conference on Logical Aspects of Computational Linguistics},
	author       = {Ljunglöf, Peter},
	year         = {2005},
}