Faculty of Information Technology, BUT

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, 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
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