Publication detail

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T.

Original Title

On the Descriptional Complexity of Scattered Context Grammars

Type

journal article in Web of Science

Language

English

Original 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.

Keywords

scattered context grammar; descriptional complexity.

Authors

MASOPUST, T.

RIV year

2009

Released

1. 1. 2009

ISBN

0304-3975

Periodical

Theoretical Computer Science

Year of study

410

Number

1

State

Kingdom of the Netherlands

Pages from

108

Pages to

112

Pages count

5

URL

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

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