Publication result detail

On the Descriptional Complexity of Scattered Context Grammars

MASOPUST, T.

Original Title

On the Descriptional Complexity of Scattered Context Grammars

English Title

On the Descriptional Complexity of Scattered Context Grammars

Type

WoS Article

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.

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

Key words in English

scattered context grammar; descriptional complexity.

Authors

MASOPUST, T.

RIV year

2010

Released

01.01.2009

ISBN

0304-3975

Periodical

Theoretical Computer Science

Volume

410

Number

1

State

Kingdom of the Netherlands

Pages from

108

Pages to

112

Pages count

5

URL

Full text in the Digital Library

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