Splicing systems (also called H systems) with a finite set of rules generate only regular languages. Thus, it is necessary to supplement such a system with a control mechanism on the use of rules. Many possibilities were explored in the literature. One fruitful idea is to use distributed architectures as suggested by the grammar systems theory. All the results obtained up to now in this area try to simulate Turing machines or type-0 Chomsky grammars by H systems with a minimal number of components. Here we approach an "orthogonal" problem: find computationally complete distributed H systems with as reduced as possible components (as the number of splicing rules; this is of practical interest, because the splicing rules correspond to restriction enzymes, and it is in general difficult to put several enzymes to work together, in the same reaction conditions). We prove that communicating splicing systems where each component consists of only one splicing rule characterize the recursively enumerable languages.
展开▼
