Detail publikace

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

MASOPUST Tomáš, MEDUNA Alexander a ŠIMÁČEK Jiří. Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars. Acta Cybernetica, roč. 18, č. 4, 2008, s. 783-793. ISSN 0324-721X.
Název česky
Dvě omezení snižující sílu zobecněných gramatik s rozptýleným kontextem
Typ
článek v časopise
Jazyk
angličtina
Autoři
URL
Abstrakt

Článek zavádí a diskutuje zobecněné gramatiky s rozptýleným kontextem založené na sekvencích pravidel, jejichž levé strany jsou tvořeny řetězci neterminálů místo standardního jednoho neterminálu. Studovány jsou dvě omezení v těchto gramatikách. První omezení vyžaduje, aby se všechny přepisované symboly jakéhokoliv derivačního kroku vyskytovaly v prvních k symbolech prvního souvislého bloku neterminálů. Druhé pak definuje derivace, jejichž jednotlivé větné formy nemají více než k neterminálů. Hlavním výsledkem článku je, že obě omezení vedou ke snížení síly těchto gramatik na sílu bezkontextových gramatik.

Rok
2008
Strany
783-793
Časopis
Acta Cybernetica, roč. 18, č. 4, ISSN 0324-721X
Kniha
Acta Cybernetica
Místo
Szeged, HU
BibTeX
@ARTICLE{FITPUB8546,
   author = "Tom\'{a}\v{s} Masopust and Alexander Meduna and Ji\v{r}\'{i} \v{S}im\'{a}\v{c}ek",
   title = "Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars",
   pages = "783--793",
   booktitle = "Acta Cybernetica",
   journal = "Acta Cybernetica",
   volume = 18,
   number = 4,
   year = 2008,
   location = "Szeged, HU",
   ISSN = "0324-721X",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8546"
}
Nahoru