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

Article type: Research Article

Authors: Masopust, Tomáš

Affiliations: Institute of Mathematics, Czech Academy of Sciences, Žižkova 22, 616 62 Brno, Czech Republic. E-mail: masopust@math.cas.cz

Abstract: 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.

Keywords: Scattered context grammars, parallel productions, descriptional complexity, generative power

DOI: 10.3233/FI-2010-258

Journal: Fundamenta Informaticae, vol. 99, no. 4, pp. 473-480, 2010