Detail publikace

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

MASOPUST, T.; MEDUNA, A.; ŠIMÁČEK, J. Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars. Acta Cybernetica, 2008, vol. 18, no. 4, p. 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
anglicky
Autoři
Masopust Tomáš, doc. RNDr., Ph.D. (CK-SZZ)
Meduna Alexandr, prof. RNDr., CSc. (UIFS)
Šimáček Jiří, Ing., Ph.D.
URL
Klíčová slova

scattered context grammar, grammatical generalization, derivation restriction, generative power.

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
BibTeX 
@article{BUT48140,
  author="Tomáš {Masopust} and Alexandr {Meduna} and Jiří {Šimáček}",
  title="Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars",
  journal="Acta Cybernetica",
  year="2008",
  volume="18",
  number="4",
  pages="783--793",
  issn="0324-721X",
  url="http://www.inf.u-szeged.hu/actacybernetica/edb/vol18n4/Masopust_2008_ActaCybernetica.xml"
}
Nahoru