J 2008

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST, Tomáš a Jiří TECHET

Základní údaje

Originální název

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Název česky

Nejlevější derivace nevymazávacích gramatik s rozptýleným kontextem: nový důkaz

Autoři

MASOPUST, Tomáš a Jiří TECHET

Vydání

Discrete Mathematics & Theoretical Computer Science, France, DMTCS, 2008, 1365-8050

Další údaje

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Odkazy

Impakt faktor

Impact factor: 1.061 v roce 2005

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

UT WoS

Klíčová slova anglicky

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

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 29. 6. 2009 15:20, doc. RNDr. Tomáš Masopust, Ph.D., DSc.

Anotace

ORIG CZ

V originále

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.

Česky

V roce 1973 V. Virkkunen dokázal, že nevymazávací gramatiky s rozptýleným kontextem, které používají nejlevější derivace, jsou stejně silné jako kontextové gramatiky. Tento článek přináší významně zjednodušený důkaz tohoto výsledku.