Publication result detail

Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way

MEDUNA, A.; TECHET, J.

Original Title

Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way

English Title

Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way

Type

Peer-reviewed article not indexed in WoS or Scopus

Original Abstract

A scattered context grammar erases nonterminals in a generalized k-limited way in a successful derivation, where k is a positive integer, if in every sentential form of a derivation, each of its substrings consisting of nonterminals from which the grammar derives empty strings is of length k or less. This paper demonstrates that if a scattered context grammar generates its sentences in this way, it can be converted to a scattered context grammar without erasing productions; in general, however, this is not possible.

English abstract

A scattered context grammar erases nonterminals in a generalized k-limited way in a successful derivation, where k is a positive integer, if in every sentential form of a derivation, each of its substrings consisting of nonterminals from which the grammar derives empty strings is of length k or less. This paper demonstrates that if a scattered context grammar generates its sentences in this way, it can be converted to a scattered context grammar without erasing productions; in general, however, this is not possible.

Keywords

scattered context grammars, erasure of nonterminals, erasing productions

Key words in English

scattered context grammars, erasure of nonterminals, erasing productions

Authors

MEDUNA, A.; TECHET, J.

RIV year

2010

Released

30.10.2008

ISBN

0001-5903

Periodical

ACTA INFORMATICA

Volume

45

Number

7

State

Federal Republic of Germany

Pages from

593

Pages to

608

Pages count

16

URL

http://www.springerlink.com/content/y23m0j1722143252/

BibTex

@article{BUT49472,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way",
  journal="ACTA INFORMATICA",
  year="2008",
  volume="45",
  number="7",
  pages="593--608",
  issn="0001-5903",
  url="http://www.springerlink.com/content/y23m0j1722143252/"
}