Detail publikace

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST, T.; TECHET, J. Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2008, vol. 10, no. 2, p. 39-46. ISSN: 1365-8050.
Název česky
Nejlevější derivace nevymazávacích gramatik s rozptýleným kontextem: nový důkaz
Typ
článek v časopise
Jazyk
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Techet Jiří, Ing., Ph.D.
URL
Klíčová slova

formální jazyky, nevymazávací gramatiky s rozptýleným kontextem, nejlevější derivace, generativní síla

Abstrakt

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.

Rok
2008
Strany
39–46
Časopis
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, roč. 10, č. 2, ISSN 1365-8050
UT WoS
000255071100001
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"
}
Nahoru