Publication Details

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST, T.; MEDUNA, A. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae, 2008, vol. 87, no. 3, p. 407-415. ISSN: 0169-2968.

Czech title

O popisné složitosti částečně paralelních gramatik

Type

journal article

Language

English

Authors

Masopust Tomáš, doc. RNDr., Ph.D. (CM-SFE)
Meduna Alexandr, prof. RNDr., CSc. (DIFS)

URL

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

Keywords

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

Abstract

In this paper, we improve some well-known results concerning descriptional complexity of partially parallel grammars. Specifically, we prove that every recursively enumerable language is generated by a four-nonterminal scattered context grammar with no more than four non-context-free productions, by a two-nonterminal multisequential grammar with no more than two selectors, or by a three-nonterminal multicontinuous grammar with no more than two selectors.

Published

2008

Pages

407–415

Journal

Fundamenta Informaticae, vol. 87, no. 3, ISSN 0169-2968

UT WoS

000262368900006

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