Small networks of polarized splicing processors are universal
- In this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. AllIn this paper, we consider the computational power of a new variant of networks of splicing processors in which each processor as well as the data navigating throughout the network are now considered to be polarized. While the polarization of every processor is predefined (negative, neutral, positive), the polarization of data is dynamically computed by means of a valuation mapping. Consequently, the protocol of communication is naturally defined by means of this polarization. We show that networks of polarized splicing processors (NPSP) of size 2 are computationally complete, which immediately settles the question of designing computationally complete NPSPs of minimal size. With two more nodes we can simulate every nondeterministic Turing machine without increasing the time complexity. Particularly, we prove that NPSP of size 4 can accept all languages in NP in polynomial time. Furthermore, another computational model that is universal, namely the 2-tag system, can be simulated by NPSP of size 3 preserving the time complexity. All these results can be obtained with NPSPs with valuations in the set as well. We finally show that Turing machines can simulate a variant of NPSPs and discuss the time complexity of this simulation.…
Author details: | Henning BordihnORCiD, Victor MitranaORCiDGND, Maria C. Negru, Andrei PaunORCiD, Mihaela PaunORCiD |
---|---|
DOI: | https://doi.org/10.1007/s11047-018-9691-0 |
ISSN: | 1567-7818 |
ISSN: | 1572-9796 |
Title of parent work (English): | Natural computing : an innovative journal bridging biosciences and computer sciences ; an international journal |
Publisher: | Springer |
Place of publishing: | Dordrecht |
Publication type: | Article |
Language: | English |
Date of first publication: | 2018/06/22 |
Publication year: | 2018 |
Release date: | 2021/06/23 |
Tag: | 2-tag system; Computing with DNA; Polarization; Splicing; Splicing processor; Turing machine |
Volume: | 17 |
Issue: | 4 |
Number of pages: | 11 |
First page: | 799 |
Last Page: | 809 |
Funding institution: | Romanian National Authority for Scientific Research and Innovation [POC P-37-257]; Alexander von Humboldt FoundationAlexander von Humboldt Foundation |
Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme |
Peer review: | Referiert |