Detail publikace

Maximal and Minimal Scattered Context Rewriting

MEDUNA Alexander a TECHET Jiří. Maximal and Minimal Scattered Context Rewriting. In: FCT 2007 Proceedings. Budapest: Springer Verlag, 2007, s. 412-423. ISSN 0302-9743.
Název česky
Maximální a minimální přepisování gramatikami s rozptýleným kontextem
Typ
článek ve sborníku konference
Jazyk
angličtina
Autoři
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Techet Jiří, Ing., Ph.D. (UIFS FIT VUT)
Klíčová slova

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

Abstrakt

Jak jejich název napovídá, během maximálního derivačního kroku přepíše gramatika s rozptýleným kontextem G maximální počet nonterminálů zatímco během minimálního derivačního kroku G přepíše minimální počet nonterminálů. V této práci je dokázáno, že pokud gramatiky s rozptýleným kontextem bez vymazávacích pravidel derivují své věty s použitím jednoho z těchto dvou derivačních kroků, potom charakterizují třídu kontextových jazyků.

Rok
2007
Strany
412-423
Časopis
Lecture Notes in Computer Science, roč. 2007, č. 4639, ISSN 0302-9743
Sborník
FCT 2007 Proceedings
Konference
16th International Symposium on Fundamentals of Computation Theory, Budapest, HU
Vydavatel
Springer Verlag
Místo
Budapest, HU
BibTeX 
@INPROCEEDINGS{FITPUB8360,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "Maximal and Minimal Scattered Context Rewriting",
   pages = "412--423",
   booktitle = "FCT 2007 Proceedings",
   journal = "Lecture Notes in Computer Science",
   volume = 2007,
   number = 4639,
   year = 2007,
   location = "Budapest, HU",
   publisher = "Springer Verlag",
   ISSN = "0302-9743",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8360"
}
Nahoru