文章基本信息

标题：Descriptional Complexity of Three-Nonterminal Scattered Context Grammars: An Improvement
本地全文：下载
作者：Tomáš Masopust ; Alexander Meduna
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2009
卷号：3
页码：183-192
DOI：10.4204/EPTCS.3.17
出版社：Open Publishing Association
摘要：Recently, it has been shown that every recursively enumerable language can be generated by a scattered context grammar with no more than three nonterminals. However, in that construction, the maximal number of nonterminals simultaneously rewritten during a derivation step depends on many factors, such as the cardinality of the alphabet of the generated language and the structure of the generated language itself. This paper improves the result by showing that the maximal number of nonterminals simultaneously rewritten during any derivation step can be limited by a small constant regardless of other factors.