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

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)

URL

http://dx.doi.org/10.1016/j.tcs.2008.10.017 HTML

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"
}