Journal article

MEDUNA Alexander and TECHET Jiří. An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations. Theoretical Computer Science. Paris: Elsevier Science, 2009, vol. 410, no. 21, pp. 1961-1969. ISSN 0304-3975.
Publication language:english
Original title:An Infinite Hierarchy of Language Families Generated by Scattered Context Grammars with n-Limited Derivations
Title (cs):Nekonečná hierarchie jazykových rodin generovaná gramatikami s rozptýleným kontextem za použití n-limitovaných derivací
Pages:1961-1969
Year:2009
Journal:Theoretical Computer Science, Vol. 410, No. 21, Paris, FR
ISSN:0304-3975
Keywords
scattered context grammars, unordered scattered context grammars, left derivation restriction, generative power, infinite hierarchy of language families
Annotation
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.
BibTeX:
@ARTICLE{
   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 = {http://www.fit.vutbr.cz/research/view_pub.php?id=8832}
}

Your IPv4 address: 54.80.18.223
Switch to IPv6 connection

DNSSEC [dnssec]