Non-preserving splicing with delay

Abstract

In this paper we investigate H systems with strongly non-preserving splicing that exhibit a new feature, namely delay, and introduce a variant of the H system that lies between H systems with strongly non-preserving splicing and H systems with non-reflexively evolving splicing. Informally, the new splicing system behaves as follows: (1) each splicing step is exactly a splicing step in a system with non-reflexively evolving splicing; and (2) the generated language is obtained exactly as in a system with strongly non-preserving splicing. For both H systems with non-reflexively evolving and non-preserving splicing we have a remarkable jump in power between systems with a finite but arbitrarily large delay, and those with infinite delay. The first can generate non-context-free languages, whereas the second do not get beyond the regular limit. Moreover, H systems with null delay generate all recursively enumerable languages.

Keywords:

• Splicing system
• Non-preserving splicing
• Non-reflexively evolving splicing
• Delay

Acknowledgements

The work of the first author was supported by research grant BES-2004-6316 of the Spanish Ministry of Education and Science.