Publication detail

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T. MEDUNA, A.

Original Title

On Descriptional Complexity of Partially Parallel Grammars

Type

journal article in Web of Science

Language

English

Original Abstract

In this paper, we improve some well-known results concerningdescriptional complexity of partially parallel grammars. Specifically,we prove that every recursively enumerable language is generated by afour-nonterminal scattered context grammar with no more than fournon-context-free productions, by a two-nonterminal multisequentialgrammar with no more than two selectors, or by a three-nonterminalmulticontinuous grammar with no more than two selectors.

Keywords

formal languages, scattered context grammars, multisequential grammars, multicontinuous grammars, descriptional complexity

Authors

MASOPUST, T.; MEDUNA, A.

RIV year

2008

Released

17. 4. 2008

ISBN

0169-2968

Periodical

Fundamenta Informaticae

Year of study

87

Number

3

State

Republic of Poland

Pages from

407

Pages to

415

Pages count

9

URL

http://fi.mimuw.edu.pl/vol87.html

BibTex

@article{BUT49466,
  author="Tomáš {Masopust} and Alexandr {Meduna}",
  title="On Descriptional Complexity of Partially Parallel Grammars",
  journal="Fundamenta Informaticae",
  year="2008",
  volume="87",
  number="3",
  pages="407--415",
  issn="0169-2968",
  url="http://fi.mimuw.edu.pl/vol87.html"
}