On the descriptional complexity of some rewriting mechanisms regulated by context conditions

We improve the upper bounds of certain descriptional complexity measures of two types of rewriting mechanisms regulated by context conditions. We prove that scattered context grammars having two context sensing productions and five nonterminals are sufficient to generate all recursively enumerable languages and we also show that the same power can be reached by simple semi-conditional grammars having 10 conditional productions with conditions of the length two or eight conditional productions with conditions of length three. The results are based on the common idea of using the so called Geffert normal forms for phrase structure grammars.