Publication Details

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.
Czech title
Dvě omezení snižující sílu zobecněných gramatik s rozptýleným kontextem
Type
journal article
Language
English
Authors
Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)
Šimáček Jiří, Ing., Ph.D.
URL
Keywords

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

Abstract

The present paper introduces and discusses generalized scattered context grammars that are based upon sequences of productions whose left-hand sides are formed by nonterminal strings, not just single nonterminals. It places two restrictions on the derivations in these grammars. More specifically, let k be a positive integer. The first restriction requires that all rewritten symbols occur within the first k symbols of the first continuous block of nonterminals in the sentential form during every derivation step. The other restriction defines derivations over sentential forms containing no more than k occurrences of nonterminals. As its main result, the paper demonstrates that both restrictions decrease the generative power of these grammars to the power of context-free grammars.

Published
2008
Pages
783–793
Journal
Acta Cybernetica, vol. 18, no. 4, ISSN 0324-721X
Book
Acta Cybernetica
Place
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"
}
Back to top