Portal de Periódicos da CAPES

Further Results on Insertion-Deletion Systems with One-Sided Contexts

2008; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-540-88282-4_31

1611-3349

Alexander Krassovitskiy, Yurii Rogozhin, Sergey Verlan,

Modular Robots and Swarm Intelligence

In this article we continue the investigation of insertion-deletion systems having a context only on one side of insertion or deletion rules. We show a counterpart of the results obtained in (Matveevici et al., 2007) by considering corresponding systems and exchanging deletion and insertion parameters. We prove three computational completeness results and one non-completeness result for these systems. We also solve the remaining open problem concerning the generative power of insertion-deletion systems having both contexts by proving the computational completeness of systems having a context-free insertion of two symbols and a contextual deletion of one symbol.