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

What is it about?

The paper mathematically proves that a special kind of formal grammars, namely Scattered Context Grammars, can describe any formal language using only context-free productions and only context-sensitive production.

Featured Image

Why is it important?

The descriptional complexity of grammars is studied from the mid of last century in formal language theory. Several years ago, it was proved that three (two) context-sensitive productions are enough and it was an open question whether just one is enough such that Turing power of scattered context grammars remains. This paper gives the positive answer.