Accepting Networks of Splicing Processors with Filtered Connections

摘要

In this paper we simplify accepting networks of splicing processors considered in [8] by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that input and output filters coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this and of the fact that splicing alone is not a very powerful operation these networks are still computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections.