Publication 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

journal article - other

Language

en

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

RIV year

2008

Released

30.10.2008

Publisher

NEUVEDEN

Location

NEUVEDEN

Pages from

593

Pages to

608

Pages count

16

URL

BibTex


@article{BUT49472,
  author="Alexandr {Meduna} and Jiří {Techet}",
  title="Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way",
  annote="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.",
  address="NEUVEDEN",
  chapter="49472",
  edition="NEUVEDEN",
  howpublished="print",
  institution="NEUVEDEN",
  journal="Acta Informatica",
  number="7",
  volume="45",
  year="2008",
  month="october",
  pages="593--608",
  publisher="NEUVEDEN",
  type="journal article - other"
}