Number of the records: 1
Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals
- 1.0345656 - MÚ 2011 RIV NL eng J - Journal Article
Masopust, Tomáš
Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals.
Fundamenta Informaticae. Roč. 99, č. 4 (2010), s. 473-480. ISSN 0169-2968. E-ISSN 1875-8681
Institutional research plan: CEZ:AV0Z10190503
Keywords : Scattered context grammars * parallel productions * descriptional complexity * generative power
Subject RIV: BA - General Mathematics
Impact factor: 0.522, year: 2010
http://iospress.metapress.com/content/f883562g5j612614/?issue=4&genre=article&spage=473&issn=0169-2968&volume=99
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.
Permanent Link: http://hdl.handle.net/11104/0186871
File Download Size Commentary Version Access Masopust4.pdf 1 71 KB Publisher’s postprint require
Number of the records: 1