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

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Techet Jiří, Ing., Ph.D. (DIFS FIT BUT)

URL

http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/93 HTML

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"
}