Detail publikace

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

MASOPUST Tomáš a TECHET Jiří. Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof. Discrete Mathematics and Theoretical Computer Science, roč. 10, č. 2, 2008, s. 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
angličtina
Autoři
Masopust Tomáš, RNDr., Ph.D. (UIFS FIT VUT)
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
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{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"
}
Nahoru