Publication Details

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T. On the Descriptional Complexity of Scattered Context Grammars. Theoretical Computer Science, 2009, vol. 410, no. 1, p. 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áš, doc. RNDr., Ph.D. (CM-SFE)

URL

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

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

UT WoS

000262997100011

BibTeX

@article{BUT49470,
  author="Tomáš {Masopust}",
  title="On the Descriptional Complexity of Scattered Context Grammars",
  journal="Theoretical Computer Science",
  year="2009",
  volume="410",
  number="1",
  pages="108--112",
  issn="0304-3975",
  url="http://dx.doi.org/10.1016/j.tcs.2008.10.017"
}