Portal de Periódicos da CAPES

Insertion-Deletion Systems with One-Sided Contexts

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

10.1007/978-3-540-74593-8_18

1611-3349

Artiom Matveevici, Yurii Rogozhin, Sergey Verlan,

Modular Robots and Swarm Intelligence

It was shown in (Verlan, 2005) that complexity measures for insertion-deletion systems need a revision and new complexity measures taking into account the sizes of both left and right context were proposed. In this article we investigate insertion-deletion systems having a context only on one side of insertion or deletion rules. We show that a minimal deletion (of one symbol) in one-symbol one-sided context is sufficient for the computational completeness if a cooperation of 4 symbols is used for insertion rules and not sufficient if an insertion of one symbol in one-symbol left and right context is used. We also prove the computational completeness for the case of the minimal context-free deletion (of two symbols) and insertion of two symbols in one-symbol one-sided context.