Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Abstract

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.