Adding Matrix Control: Insertion-Deletion Systems with Substitutions Ⅲ

摘要

We discuss substitutions as a further type of operations, added to matrix insertion-deletion systems. For such systems, we additionally discuss the effect of appearance checking. This way, we obtain new characterizations of the families of context-sensitive and the family of recursively enumerable languages. To reach computational completeness, not much context is needed for systems with appearance checking.