Descriptional Complexity of Scattered Rewriting and Multirewriting: An Overview

During a derivation step, partially parallel grammars rewrite some symbols of the sentential form while leaving the others unrewritten. The present paper discusses grammars that perform two types of this parallelism - scattered rewriting and multirewriting. It gives an overview of the main results concerning their descriptional complexity with respect to the number of nonterminals or productions. In the conclusion, some open problems are pointed out.