Further results on insertion-deletion systems with one-sided contexts. (English)
Martín-Vide, Carlos (ed.) et al., Language and automata theory and applications. Second international conference, LATA 2008, Tarragona, Spain, March 13‒19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-88281-7/pbk). Lecture Notes in Computer Science 5196, 333-344 (2008).
Summary: 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 [{\it A. Matveevici}, {\it Y. Rogozhin} and {\it S. Verlan}, “Insertion-deletion systems with one-sided contexts", Lect. Notes Comput. Sci. 4664, 205‒217 (2007; Zbl 1155.68419)] 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.