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

MASOPUST, Tomáš. Bounded Number of Parallel Productions in Scattered Context Grammars with Three Nonterminals. Fundamenta Informaticae. Poland: IOS Press, The Netherlands, 2010, vol. 99, No 4, p. 473-480. ISSN 0169-2968.

Basic information

Original name

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

Authors

MASOPUST, Tomáš

Edition

Fundamenta Informaticae, Poland, IOS Press, The Netherlands, 2010, 0169-2968

---

Other information

Language

English

Type of outcome

Article in a journal

Field of Study

10201 Computer sciences, information science, bioinformatics

Confidentiality degree

is not subject to a state or trade secret

References:

URL

Impact factor

Impact factor: 0.522

Organization unit

Faculty of Informatics

UT WoS

000279638200005

Keywords in English

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

Tags

International impact, Reviewed

---

Abstract

In the original language

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.