Publication Details

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST Tomáš and TECHET Jiří. Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof. Discrete Mathematics and Theoretical Computer Science, vol. 10, no. 2, 2008, pp. 39-46. ISSN 1365-8050.
Czech title
Nejlevější derivace nevymazávacích gramatik s rozptýleným kontextem: nový důkaz
Type
journal article
Language
english
Authors
URL
Keywords

formal languages, propagating scattered context grammars, leftmost derivations, generative power

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.

Published
2008
Pages
39-46
Journal
Discrete Mathematics and Theoretical Computer Science, vol. 10, no. 2, ISSN 1365-8050
UT WoS
000255071100001
BibTeX
@ARTICLE{FITPUB8600,
   author = "Tom\'{a}\v{s} Masopust and Ji\v{r}\'{i} Techet",
   title = "Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof",
   pages = "39--46",
   journal = "Discrete Mathematics and Theoretical Computer Science",
   volume = 10,
   number = 2,
   year = 2008,
   ISSN = "1365-8050",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8600"
}
Back to top