Faculty of Information Technology, BUT

Publication Details

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

MEDUNA Alexander and TECHET Jiří. Scattered Context Grammars that Erase Nonterminals in a Generalized k-Limited Way. Acta Informatica, vol. 45, no. 7, pp. 593-608. ISSN 0001-5903.
Czech title
Gramatiky s rozptýleným kontextem vymazávající nonterminály zobecněným k-limitovaným způsobem
Type
journal article
Language
english
Authors
URL
Keywords
scattered context grammars, erasure of nonterminals, erasing productions
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.
Published
2008
Pages
593-608
Journal
Acta Informatica, vol. 45, no. 7, ISSN 0001-5903
Publisher
Springer Verlag
BibTeX
@ARTICLE{FITPUB8787,
   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 = "https://www.fit.vut.cz/research/publication/8787"
}
Back to top