Detail publikačního výsledku

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

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

Originální název

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

Anglický název

Two Power-Decreasing Derivation Restrictions in Generalized Scattered Context Grammars

Druh

Článek recenzovaný mimo WoS a Scopus

Originální abstrakt

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.

Anglický abstrakt

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.

Klíčová slova

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

Klíčová slova v angličtině

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

Autoři

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

Rok RIV

2010

Vydáno

18.01.2008

Místo

Szeged

Kniha

Acta Cybernetica

ISSN

0324-721X

Periodikum

Acta Cybernetica

Svazek

18

Číslo

4

Stát

Maďarsko

Strany od

783

Strany do

793

Strany počet

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