Graph-Controlled Insertion-Deletion Systems

Abstract

In this article, we consider the operations of insertion and deletion working in a graph-controlled manner. We show that like in the case of context-free productions, the computational power is strictly increased when using a control graph: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and with the control graph having only four nodes.

In Proceedings DCFS 2010, arXiv:1008.1270

References in corpus (1)

• Computational Power of P Systems with Small Size Insertion and Deletion Rules

Cited by in corpus (1)

• Matrix Insertion-Deletion Systems