A polynomial time extension of parallel multiple context-free grammar

• 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Språkteknologi (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Language Technology (hsv//eng)

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)