Skip to Main content Skip to Navigation
Journal articles

Leftmost derivations of propagating scattered context grammars: a new proof

Abstract : In 1973, V. 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-00972321
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, April 3, 2014 - 4:10:40 PM
Last modification on : Wednesday, November 18, 2020 - 5:34:02 PM
Long-term archiving on: : Thursday, July 3, 2014 - 4:35:26 PM

File

712-3269-2-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00972321, version 1

Collections

Citation

Tomáš Masopust, Jiří Techet. Leftmost derivations of propagating scattered context grammars: a new proof. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2008, 10 (2), pp.39--46. ⟨hal-00972321⟩

Share

Metrics

Record views

240

Files downloads

819