Detail publikace

A Note on Scattered Context Grammars with Non-Context-Free Components

TECHET Jiří. A Note on Scattered Context Grammars with Non-Context-Free Components. In: MEMICS 2007 Proceedings. Znojmo: Ing. Zdeněk Novotný, CSc., 2007, s. 225-232. ISBN 978-80-7355-077-6.
Název česky
O gramatikách s rozptýleným kontextem s jinými než bezkontextovými komponentami
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
Klíčová slova

formální jazyky, gramatiky s rozptýleným kontextem, generativní síla

Abstrakt

Gramatiky s rozptýlemým kontextem, zavedené jako přímočaré rozšíření bezkontextových gramatik, aplikují při generování svých vět paralelně n bezkontextoých pravidel. Tato práce diskutuje jejich omezení, ve kterých jsou všechny komponenty pravidel gramatik s rozptýleným kontextem buď lineární nebo pravě lineární. Je ukázáno, že rodiny jazyků generovaných těmito gramatikami jsou ekvivalentní rodinám generovaným lineárními a pravě lineárními jednoduchými maticovými gramatikami.  Nakonec je zmíněna síla gramatik s rozptýleným kontextem s kontextovými a neomezenými pravidly a jsou diskutovány některé otevřené problémy.

Rok
2007
Strany
225-232
Sborník
MEMICS 2007 Proceedings
Konference
MEMICS'07 -- 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Znojmo, CZ
ISBN
978-80-7355-077-6
Vydavatel
Ing. Zdeněk Novotný, CSc.
Místo
Znojmo, CZ
BibTeX 
@INPROCEEDINGS{FITPUB8460,
   author = "Ji\v{r}\'{i} Techet",
   title = "A Note on Scattered Context Grammars with Non-Context-Free Components",
   pages = "225--232",
   booktitle = "MEMICS 2007 Proceedings",
   year = 2007,
   location = "Znojmo, CZ",
   publisher = "Ing. Zden\v{e}k Novotn\'{y}, CSc.",
   ISBN = "978-80-7355-077-6",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8460"
}
Nahoru