Further Results on Insertion-Deletion Systems with One-Sided Contexts
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.
Published in 2008.