RNA-Editing with Combined Insertion and Deletion Preserves Regularity
E.P. de Vink, H. Zantema and D. Bosnacki 

We consider two elementary forms of string rewriting called guided
insertion/deletion and guided rewriting. The original strings are modified
depending on the match with a given set of auxiliary strings, called guides.
Guided insertion/deletion considers matching of a string and a guide with
respect to a specific correspondence of strings, guided rewriting considers
matching of a string and a guide with respect to an equivalence relation on
the alphabet. Guided insertion/deletion is inspired by RNA-editing, a
biological process by which the original genetic information stored in DNA is
modified before its final expression. The formalism here allows for
simultaneous insertion and deletion of string elements. Guided rewriting,
based on a letter-to-letter relation, is technically more appealing than
guided insertion/deletion. We prove that guided rewriting preserves
regularity: for every regular language its closure under guided rewriting is
regular too. In the proof we will rely on the auxiliary notion of a slice
sequence. We establish a correspondence of slice sequences and guide rewrite
sequences. Because of their left-to-right nature, slice sequences are more
convenient to deal with than guided rewrite sequences in the construction of
the finite automata that we encounter in the proofs of regularity. Based on
the result for guided rewriting we establish that guided insertion/deletion
preserves regularity as well.