Graph-Controlled Insertion-Deletion Systems

Rudolf Freund
Marian Kogler
Yurii Rogozhin
Sergey Verlan

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 Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 88–98.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.11 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org