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

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. [ABSTRACT FROM AUTHOR]