Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: parallel productions

Sortuj według:

Ogranicz wyniki do:

Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Křivka Zbyněk, Meduna Alexander

Fundamenta Informaticae

2021

Vol. 179, nr 4

361--384

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

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

Masopust T.

Fundamenta Informaticae

2010

Vol. 99, nr 4

473-480

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.