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