Publication Details

On Descriptional Complexity of Partially Parallel Grammars

MASOPUST Tomáš and MEDUNA Alexander. On Descriptional Complexity of Partially Parallel Grammars. Fundamenta Informaticae, vol. 87, no. 3, 2008, pp. 407-415. ISSN 0169-2968.

Czech title

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

Type

journal article

Language

english

Authors

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)
Meduna Alexander, prof. RNDr., CSc. (DIFS FIT BUT)

URL

http://fi.mimuw.edu.pl/vol87.html 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

Publisher

IOS Press

UT WoS

000262368900006

BibTeX

@ARTICLE{FITPUB8605,
   author = "Tom\'{a}\v{s} Masopust and Alexander Meduna",
   title = "On Descriptional Complexity of Partially Parallel Grammars",
   pages = "407--415",
   journal = "Fundamenta Informaticae",
   volume = 87,
   number = 3,
   year = 2008,
   ISSN = "0169-2968",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8605"
}