Journal articleMEDUNA Alexander and TECHET Jiří. Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way. Acta Informatica. 2008, vol. 45, no. 7, pp. 593-608. ISSN 0001-5903. | Publication language: | english |
---|
Original title: | Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way |
---|
Title (cs): | Gramatiky s rozptýleným kontextem vymazávající nonterminály zobecněným k-limitovaným způsobem |
---|
Pages: | 593-608 |
---|
Year: | 2008 |
---|
Journal: | Acta Informatica, Vol. 45, No. 7, DE |
---|
ISSN: | 0001-5903 |
---|
URL: | http://www.springerlink.com/content/y23m0j1722143252/ [HTML] |
---|
Keywords |
---|
scattered context grammars, erasure of
nonterminals, erasing productions |
Annotation |
---|
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. |
BibTeX: |
---|
@ARTICLE{
author = {Alexander Meduna and Ji{\v{r}}{\'{i}} Techet},
title = {Scattered Context Grammars that Erase Nonterminals in a
Generalized k-Limited Way},
pages = {593--608},
journal = {Acta Informatica},
volume = {45},
number = {7},
year = {2008},
ISSN = {0001-5903},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php.en.iso-8859-2?id=8787}
} |
|