Publication Details

Descriptional Complexity of Multi-Parallel Grammars

MASOPUST Tomáš. Descriptional Complexity of Multi-Parallel Grammars. Information Processing Letters, vol. 108, no. 2, 2008, pp. 68-70. ISSN 0020-0190.

Czech title

Popisná složitost multi-paralelních gramatik

Type

journal article

Language

english

Authors

Masopust Tomáš, RNDr., Ph.D. (DIFS FIT BUT)

URL

http://dx.doi.org/10.1016/j.ipl.2008.04.002 HTML

Keywords

formal languages, multi-parallel grammars, descriptional complexity

Abstract

This paper studies the descriptional complexity of multi-parallel grammars with respect to the number of nonterminals and selectors, and the length of these selectors. As a result, it proves that every recursively enumerable language is generated by a multi-parallel grammar with no more than seven nonterminals and four selectors of length five.

Published

2008

Pages

68-70

Journal

Information Processing Letters, vol. 108, no. 2, ISSN 0020-0190

Publisher

Elsevier Science

UT WoS

000259435800005

BibTeX

@ARTICLE{FITPUB8593,
   author = "Tom\'{a}\v{s} Masopust",
   title = "Descriptional Complexity of Multi-Parallel Grammars",
   pages = "68--70",
   journal = "Information Processing Letters",
   volume = 108,
   number = 2,
   year = 2008,
   ISSN = "0020-0190",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/8593"
}