Publication result detail

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

MASOPUST, T.; MEDUNA, A.; ŠIMÁČEK, J.

Original Title

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

English Title

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

Type

Peer-reviewed article not indexed in WoS or Scopus

Original 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.

English 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.

Keywords

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

Key words in English

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

Authors

MASOPUST, T.; MEDUNA, A.; ŠIMÁČEK, J.

RIV year

2010

Released

18.01.2008

Location

Szeged

Book

Acta Cybernetica

ISBN

0324-721X

Periodical

Acta Cybernetica

Volume

18

Number

4

State

Hungary

Pages from

783

Pages to

793

Pages count

11

URL

http://www.inf.u-szeged.hu/actacybernetica/edb/vol18n4/Masopust_2008_ActaCybernetica.xml

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"
}