Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals

Number of the records: 1

1.

SYSNO ASEP	0345656
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
Author(s)	Masopust, Tomáš (MU-W)_{RID, ORCID, SAI}
Source Title	Fundamenta Informaticae. - : IOS Press - ISSN 0169-2968 Roč. 99, č. 4 (2010), s. 473-480
Number of pages	8 s.
Language	eng - English
Country	NL - Netherlands
Keywords	Scattered context grammars ; parallel productions ; descriptional complexity ; generative power
Subject RIV	BA - General Mathematics
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000279638200005
EID SCOPUS	77954729583
DOI	10.3233/FI-2010-258
Annotation	Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1