Locally evolving splicing systems

An extended H system with locally evolving rules is a model of splicing computation with a special feature that the splicing rules evolve at each step. It was originally proved by Paun et al. that all RE languages can be generated by such systems with a finite set of rules of radius at most 4 and with contexts of length at most 7 for the insertion-deletion rules by which the splicing rules evolve. We improve this result by reducing the length of the contexts to at most 2 and we also show that such systems with radius at most 2 and contexts of length at most 3 can generate all RE languages. In both cases, the insertion-deletion rules will insert or delete only one symbol. We also show that if the inserted strings are of length at most 2 and the deleted strings are of length 1, then the system can generate all RE languages with splicing rules of radius 3 and insertion-deletion rules with contexts of length at most 2. Finally, we show that the length of contexts and of the strings inserted/deleted can be reduced to 1 if the rules are applied in a matrix controlled manner.