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

English Title

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Type

journal article in Web of Science

Language

en

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.

English 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

RIV year

2008

Released

11.04.2008

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

39

Pages to

46

Pages count

8

URL

Documents

BibTex


@article{BUT48169,
  author="Tomáš {Masopust} and Jiří {Techet}",
  title="Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof",
  annote="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.",
  address="NEUVEDEN",
  chapter="48169",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE",
  number="2",
  volume="10",
  year="2008",
  month="april",
  pages="39--46",
  publisher="NEUVEDEN",
  type="journal article in Web of Science"
}