Publication Details

An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations

MEDUNA Alexander and TECHET Jiří. An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations. Theoretical Computer Science, vol. 410, no. 21, 2009, pp. 1961-1969. ISSN 0304-3975.
Czech title
Nekonečná hierarchie jazykových rodin generovaná gramatikami s rozptýleným kontextem za použití n-limitovaných derivací
Type
journal article
Language
english
Authors
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)
Techet Jiří, Ing., Ph.D. (DIFS FIT BUT)
Keywords

scattered context grammars, unordered scattered context grammars, left derivation restriction, generative power, infinite hierarchy of language families

Abstract

This paper introduces scattered context grammars without erasing productions, in which an application of a production always occurs within the first n nonterminals of the current sentential form. It demonstrates that this restriction gives rise to an infinite hierarchy of language families each of which is properly included in the family of context-sensitive languages. In addition, it proves analogous results for unordered scattered context grammars. Some consequences of these results are derived and open problems formulated.

Published
2009
Pages
1961-1969
Journal
Theoretical Computer Science, vol. 410, no. 21, ISSN 0304-3975
Publisher
Elsevier Science
BibTeX 
@ARTICLE{FITPUB8832,
   author = "Alexander Meduna and Ji\v{r}\'{i} Techet",
   title = "An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations",
   pages = "1961--1969",
   journal = "Theoretical Computer Science",
   volume = 410,
   number = 21,
   year = 2009,
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8832"
}
Back to top