Publication Details

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST Tomáš. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science, vol. 410, no. 1, 2009, pp. 108-112. ISSN 0304-3975.
Czech title
O popisné složitosti gramatik s rozptýleným kontextem
Type
journal article
Language
english
Authors
URL
Keywords

scattered context grammar; descriptional complexity.

Abstract

This paper proves that every recursively enumerable language is generated by a scattered context grammar with no more than four nonterminals and three non-context-free productions. In its conclusion, it gives an overview of the results and open problems concerning scattered context grammars and languages.

Published
2009
Pages
108-112
Journal
Theoretical Computer Science, vol. 410, no. 1, ISSN 0304-3975
Publisher
Elsevier Science
UT WoS
000262997100011
BibTeX
@ARTICLE{FITPUB8778,
   author = "Tom\'{a}\v{s} Masopust",
   title = "On the Descriptional Complexity of Scattered Context Grammars",
   pages = "108--112",
   journal = "Theoretical Computer Science",
   volume = 410,
   number = 1,
   year = 2009,
   ISSN = "0304-3975",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8778"
}
Back to top