Discrete Mathematics & Theoretical Computer Science, Vol 10, No 2 (2008)

Font Size:  Small  Medium  Large

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Tomas Masopust, Jiri Techet


In 1973, Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.

Full Text: PDF PostScript