Publication detail
Descriptional Complexity of Multi-Parallel Grammars
MASOPUST, T.
Original Title
Descriptional Complexity of Multi-Parallel Grammars
Type
journal article in Web of Science
Language
English
Original 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.
Keywords
formal languages, multi-parallel grammars, descriptional complexity
Authors
MASOPUST, T.
RIV year
2008
Released
31. 3. 2008
ISBN
0020-0190
Periodical
Information Processing Letters
Year of study
108
Number
2
State
Kingdom of the Netherlands
Pages from
68
Pages to
70
Pages count
3
URL
BibTex
@article{BUT48168,
author="Tomáš {Masopust}",
title="Descriptional Complexity of Multi-Parallel Grammars",
journal="Information Processing Letters",
year="2008",
volume="108",
number="2",
pages="68--70",
issn="0020-0190",
url="http://dx.doi.org/10.1016/j.ipl.2008.04.002"
}