Publication detail

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST, T. TECHET, J.

Original Title

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Type

journal article in Web of Science

Language

English

Original 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.

Keywords

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

Authors

MASOPUST, T.; TECHET, J.

RIV year

2008

Released

11. 4. 2008

ISBN

1365-8050

Periodical

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

Year of study

10

Number

2

State

French Republic

Pages from

39

Pages to

46

Pages count

8

URL

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

BibTex

@article{BUT48169,
  author="Tomáš {Masopust} and Jiří {Techet}",
  title="Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof",
  journal="DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE",
  year="2008",
  volume="10",
  number="2",
  pages="39--46",
  issn="1365-8050",
  url="http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/93"
}