Search

Spiking neural P systems (SNP systems) are a class of distributed and parallel computation models, which are inspired by the way in which neurons process information by means of spikes, where a neuron fires and distributes the spikes to all the neurons linked by synapses with the firing neuron. In this work, a new spike distribution mechanism is introduced, where the produced spikes are distributed to a set of neurons indicated by the target indications. The computation power of SNP systems with this new spike distribution mechanism is investigated. It is demonstrated that SNP systems with such a distribution mechanism are Turing universal as both number generators and function computing devices. Moreover, it is shown that 6 neurons (respectively, 15 neurons) are sufficient for constructing a universal SNP system with the proposed spike distribution mechanism as a number generator (respectively, as a function computing device). By comparing with the classical one, it can be found that the proposed spike distribution mechanism is a powerful feature in terms of the number of neurons used to construct universal SNP systems.

Toehold-mediated DNA strand displacement endows DNA nanostructures with dynamic response capability. However, the complexity of sequence design dramatically increases as the size of the DNA network increases. We attribute this problem to the mechanism of toehold-mediated strand displacement, termed exact strand displacement (ESD), in which one input strand corresponds to one specific substrate. In this work, we propose an alternative to toehold-mediated DNA strand displacement, termed fuzzy strand displacement (FSD), in which one-to-many and many-to-one relationships are established between the input strand and the substrate, to reduce the complexity. We have constructed four modules, termed converter, reporter, fuzzy detector, and fuzzy trigger, and demonstrated that a sequence pattern recognition network composed of these modules requires less complex sequence design than an equivalent network based on toehold-mediated DNA strand displacement.

This paper proposes a novel connected components labeling (CCL) approach that introduces a gamma signal to record certain mask pixels’ values to eliminate duplicated pixel checking and regulate the labeling process for higher efficiency. A new block-based two-scan CCL algorithm, Eight-Connected Gamma-Signal-regulated (ECGS) algorithm, is designed and developed by applying this approach to evaluate a block of 2 × 2 pixels (with just 6 mask pixels) in each iteration such that the total number of operations is considerably reduced and the labeling efficiency is significantly improved. The experiments conducted on a public benchmark, YACCLAB (Yet Another Connected Components Labeling Benchmark), have demonstrated that the proposed ECGS algorithm can outperform current state-of-the-art CCL algorithms for a number of digital images.

Spiking neural P systems (SN P systems) are a class of parallel computing models, inspired by the way in which neurons process information and communicate to each other by means of spikes. In this work, we consider a variant of SN P systems, SN P systems with polarizations (PSN P systems), where the integrate-and-fire conditions are associated with polarizations of neurons. The computation power of PSN P systems working in the asynchronous mode (at a computation step, a neuron with enabled rules does not obligatorily fire), instead of the synchronous mode (a neuron with enabled rules should fire), is investigated. We proved that asynchronous PSN P systems with extended rules (the application of a rule can produce more than one spikes) or standard rules (all rules can only produce a spike) can both characterize partially blind counter machines, hence, such systems are not Turing universal. The equivalence of the computation power of asynchronous PSN P systems in both cases of using extended rules or standard rules indicates that asynchronous PSN P systems are robust in terms of the amount of information exchanged among neurons. It is known that synchronous PSN P systems with standard rules are Turing universal, so these results also suggest that the working model, synchronization or asynchronization, is an essential ingredient for a PSN P system to achieve a powerful computation capability.

Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). .ese borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. .is paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. .ese optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model. National Natural Science Foundation of China 61772214 National Natural Science Foundation of China 61602192 National Natural Science Foundation of China 61320106005 Hunan Provincial Natural Science Foundation of China 2020JJ4215 Agencia Estatal de Investigación TIN2017-89842-P

In nature, allostery is the principal approach for regulating cellular processes and pathways. Inspired by nature, structure-switching aptamer-based nanodevices are widely used in artificial biotechnologies. However, the canonical aptamer structures in the nanodevices usually adopt a duplex form, which limits the flexibility and controllability. Here, a new regulating strategy based on a clamp-like triplex aptamer structure (CLTAS) was proposed for switching DNA polymerase activity via conformational changes. It was demonstrated that the polymerase activity could be regulated by either adjusting structure parameters or dynamic reactions including strand displacement or enzymatic digestion. Compared with the duplex aptamer structure, the CLTAS possesses programmability, excellent affinity and high discrimination efficiency. The CLTAS was successfully applied to distinguish single-base mismatches. The strategy expands the application scope of triplex structures and shows potential in biosensing and programmable nanomachines.

In the majority of models of P systems, rules are applied at the ticks of a global clock and their products are introduced into the system for the following step. In timed P systems, di erent integer durations are statically assigned to rules; time-free P systems are P systems yielding the same languages independently of these durations. In clock-free P systems, durations are real and are assigned to individual rule applications; thus, different applications of the same rule may last for a different amount of time. In this paper, we formalise timed, time-free, and clock-free P system within a framework for generalised parallel rewriting. We then explore the relationship between these variants of semantics. We show that clock-free P systems cannot effi ciently solve intractable problems. Moreover, we consider un-timed systems where we collect the results using arbitrary timing functions as well as un-clocked P systems where we take the union over all possible per-instance rule durations. Finally, we also introduce and study mode-free P systems, whose results do not depend on the choice of a mode within a fixed family of modes, and compare mode-freeness with clock-freeness.

P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a normal form of P systemswith active membranes, called cell-like P systems with polarizations and minimal rules,where rules are minimal in the sense that an object evolves to exactly one object withthe application of an evolution rule or a communication rule, or an object evolves to twoobjects that are assigned to the two new generated membranes by applying a division rule.The present work investigates the computational power of P systems with polarizationsand minimal rules. Specifically, results about Turing universality and non-universality areobtained with the combination of the number of membranes, the number of polarizations,and the types of rules. We also show that polarizationless P systems with minimal rules areequivalent to Turing machines working in a polynomial space, that is, the class of problemsthat can be solved in polynomial time by polarizationless P systems with minimal rules isequal to the classPSPACE. Ministerio de Economía, Industria y Competitividad TIN2017-89842-P (MABICAP)

Tissue P systems with channel states are a class of parallel computing models, where the communication between two regions is regulated by a channel state, and at a computation step the state of a channel can evolve to one of the arbitrarily many states. In this work, we limit the “arbitrarily many states of a channel” to “two states of a channel”. Such a variant of P systems is called tissue P systems with flip-flop channel states (TPFFCSs). The computation power of TPFFCSs is studied. We show that TPFFCSs with arbitrarily many cells and antiport rules of length 2 are able to compute only finite sets of non-negative integers. However, TPFFCSs with two cells, antiport rules of length 3, or symport rules of length 2, or symport rules of length 1 and antiport rules of length 2 are proved to be Turing universal.

Contextual array P systems generate two-dimensional picture arrays by sequential application of contextual array rules on picture arrays. Here we consider a parallel mode of application of the contextual array rules in the regions of such an array P system. We call the resulting array P system as parallel contextual array P system (PCAP) and we study the generative power of these systems. A main advantage is that the number of membranes needed in the constructions of the PCAP for picture array generation is reduced in comparison with the sequential counterpart.

Tissue P systems with evolutional communication rules and cell division (TPec, for short) are a class of bio-inspired parallel computational models, which can solve NP-complete problems in a feasible time. In this work, a variant of TPec, called $k$-distributed tissue P systems with evolutional communication and cell division ($k\text{-}\Delta_{TP_{ec}}$, for short) is proposed. A uniform solution to the SAT problem by $k\text{-}\Delta_{TP_{ec}}$ under balanced fixed-partition is presented. The solution provides not only the precise satisfying truth assignments for all Boolean formulas, but also a precise amount of possible such satisfying truth assignments. It is shown that the communication resource for one-way and two-way uniform $k$-P protocols are increased with respect to $k$; while a single communication is shown to be possible for bi-directional uniform $k$-P protocols for any $k$. We further show that if the number of clauses is at least equal to the square of the number of variables of the given boolean formula, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem are more efficient than TPec as show in \cite{bosheng2017}; if the number of clauses is equal to the number of variables, then $k\text{-}\Delta_{TP_{ec}}$ for solving the SAT problem work no much faster than TPec.

Numerical P systems (NP systems) are a class of computing models inspired both from the structure of living cells and the economic reality. Enzymatic numerical P systems (ENP systems) are a variant of NP systems, which were successfully applied in autonomous robot control. In this work, we investigate the computational power of ENP systems working in the sequential mode: both non-deterministically sequential and deterministically sequential systems are considered. For non-deterministically sequential ENP systems, we improve a known universality result by reducing the number of membranes and programs used in the universal system from 7 to 2 and 19 to 8, respectively. For deterministically sequential ENP systems, we prove that they are Turing universal even when linear production functions are used and each function has at most two variables. As a byproduct, we obtain a small deterministic universal enzymatic numerical P system with 23 membranes and 118 programs by simulating a specific universal register machine. These results give a positive answer to an open problem formulated in Gh. Paun (2014) [37] .

An operation on strings, called flat splicing was introduced, inspired by a splicing operation on circular strings considered in the study of modelling of the recombinant behaviour of DNA molecules. A simple kind of flat splicing, called alphabetic flat splicing, allows insertion of a word with a specified start symbol and/or a specified end symbol, between two pre-determined symbols in a given word. In this work, we consider a P system with only alphabetic flat splicing rules as the evolution rules and strings of symbols as objects in its regions. We examine the language generative power of the resulting alphabetic flat splicing P systems (AFS P systems, for short). In particular, we show that AFS P systems with two membranes are more powerful in generative power than AFS P systems with a single membrane. We also construct AFS P systems with at most three membranes to generate languages that do not belong to certain other language classes and show an application to generation of chain code pictures.

Calibration devices in an automatic verification system are used to verify the accuracy of electricity smart meters. As time goes by, calibration devices may experience the metering performance degradation, making results of error tests biased. Therefore, it is of great significance to ensure calibration devices have qualified metering performance. Conventionally, their performance could only be manually inspected at regular intervals, while keep unknown during the operation. To address this issue, an on-line anomaly identifying method based on calibration devices’ parallel working mode is proposed to check their metering performance in real time. Instead of off-line inspections, a device’s metering performance is associated with the corresponding results of error tests, and comparisons among distributions based on results corresponding to different calibration devices would provide evidences to identify the ones having metering performance unqualified without interrupting the verification tasks. In addition, a case study is conducted to prove the validity.

Community detection problem in networks has received a great deal of attention during the past decade. Most of community detection algorithms took into account only positive links, but they are not suitable for signed networks. In our work, we propose an algorithm based on random walks for community detection in signed networks. Firstly, the local maximum degree node which has a larger degree compared with its neighbors is identified, and the initial communities are detected based on local maximum degree nodes. Then, we calculate a probability for the node to be attracted into a community by positive links based on random walks, as well as a probability for the node to be away from the community on the basis of negative links. If the former probability is larger than the latter, then it is added into a community; otherwise, the node could not be added into any current communities, and a new initial community may be identified. Finally, we use the community optimization method to merge similar communities. The proposed algorithm makes full use of both positive and negative links to enhance its performance. Experimental results on both synthetic and real-world signed networks demonstrate the effectiveness of the proposed algorithm.

Numerical P systems (for short, NP systems) are distributed and parallel computing models inspired both from the structure of living cells and from the economic reality, where the values of variables evolve by programs that are composed by production functions and repartition protocols: the value of a production function is distributed to variables according to the corresponding repartition protocol. In this work, we introduce a new method of using evolution programs into NP systems, where thresholds are associated with production functions. The computation power of NP systems with production thresholds is investigated. Specifically, we prove that NP systems with lower-thresholds (the production function value can be distributed only when it is not smaller than a given constant), with one membrane working both in the all-parallel mode and in the sequential mode, are universal. The universal results of NP systems with lower-thresholds are extended to NP systems with upper-thresholds (the production function value can be distributed only when it is not greater than a given constant) by simulating the former with the latter. These universality results show that NP systems with production thresholds have the potential to implement any computer program or robot behavior.

Tissue P systems with symport/antiport rules are a class of distributed parallel computing models inspired by the cell intercommunication in tissues, where objects are never modified in the process of communication, just changing their place within the system. In this work, a variant of tissue P systems, called tissue P systems with evolutional symport/antiport rules is introduced, where objects are moved from one region to another region and may be evolved during this process. The computational power of such P systems is studied. Specifically, it is proved that such P systems with one cell and using evolutional symport rules of length at most 3 or using evolutional antiport rules of length at most 4 are Turing universal (only the family of all finite sets of positive integers can be generated by such P systems if standard symport/antiport rules are used). Moreover, cell division rules are considered in tissue P systems with evolutional symport/antiport rules, and a limit on the efficiency of such P systems is provided with evolutional communication rules of length at most 2. The computational efficiency of this kind of models is shown when using evolutional communication rules of length at most 4.

DNA strand displacement is widely used in DNA-related nanoengineering for its remarkable specificity and predictability. We report a nicking enzyme-assisted mechanism to regulate strand displacement, where DNA toeholds are dynamically controlled. To demonstrate the strategy, a protein/DNA-based Boolean operation system is constructed and based on it a two-channel multiplexer controlled by three different nicking enzymes is realized. The proposed regulatory mechanism can be used for switch logic statement and bridges protein and DNA logic circuits.

Synthetic catalytic DNA circuits are important signal amplification tools for molecular programming due to their robust and modular properties. In catalytic circuits, the reactant recycling operation is essential to facilitate continuous processes. Therefore, it is desirable to develop new methods for the recycling of reactants and to improve the recyclability in entropy-driven DNA circuit reactions. Here, we describe the implementation of a nicking-assisted recycling strategy for reactants in entropy-driven DNA circuits, in which duplex DNA waste products are able to revert into active components that could participate in the next reaction cycle. Both a single-layered circuit and multiple two-layered circuits of different designs were constructed and analyzed. During the reaction, the single-layered catalytic circuit can consume excess fuel DNA strands without depleting the gate components. The recycling of the two-layered circuits occurs during the fuel DNA digestion but not during the release of the downstream trigger. This strategy provides a simple yet versatile method for creating more efficient entropy-driven DNA circuits for molecular programming and synthetic biology.

We propose synthetic DNA/RNA transcription circuits based on specific aptamer recognition. By mimicking transcription factor regulation, combined with specific enzyme/DNA aptamer binding, multiple biomolecules including DNA, RNA, polymerase, restriction enzymes and methylase were used as regulators. In addition, multi-level cascading networks and methylation-switch circuits were also established. This regulation strategy has the potential to expand the toolkit of in vitro synthetic biology.

Single-stranded tile (SST) strategy offers precise control over the circumferences of nanotubes while the kinetic trap in the process of the self-assembly prevents the formation of wider tubes. Here, we report a simple and efficient method to build DNA nanotubes using only 2 SSTs via one-pot annealing. The diameters of the 2-SST nanotubes were much larger than what the kinetic trap theory would predict, indicating a new mechanism was at play in the formation of these nanotubes. Further investigation suggested that the 2-SST nanotubes were assembled through a hierarchical pathway that involved an intermediate formation of 2-SST nano-lines.

Numerical P systems are a class of P systems inspired both from the structure of living cells and from economics, where variables are associated with the membranes, and these associations are not changed during the computation. However, in the standard P systems, a crucial character for objects is that they can pass through membranes, between regions of the same cell, between cells, or between cells and their environment. We introduce this character also to numerical P systems, and call the new variant numerical P systems with migrating variables (MNP systems). The computational power of MNP systems is investigated both as number generators and as string generators, working in the one-parallel or the sequential modes. Specially, as number generators, MNP systems are proved to be universal working in the above two modes. As string generators, the generative capacity of such systems is investigated having as a reference the families of languages in the Chomsky hierarchy, and a characterization of recursively enumerable languages is obtained.

In search of the borderline between universality and non-universality of purely catalytic P systems, we prove that purely catalytic P systems with one catalyst are universal when inhibitors plus promoters or a priority relation among the rules plus promoters are used. The universality is also obtained for purely catalytic cooperating P systems with two catalysts (without any control on the use of rules). Some related open problems are also formulated.

Cell-like spiking neural P systems are a variant of standard spiking neural P systems, which have a cell-like instead of neural-like architecture. It has been proved that cell-like spiking neural P systems can generate Turing computable sets of numbers. In this work, the computational power of cell-like spiking neural P systems as language generators is investigated. Characterization of finite languages is obtained with cell-like spiking neural P systems when the number of spikes produced is less than the number of spikes consumed, and characterization of recursively enumerable languages is obtained by cell-like spiking neural P systems when there is no restriction on the number of produced spikes. The relationships of the languages generated by cell-like spiking neural P systems with regular, non-context-free and non-semilinear languages are also investigated.

Spiking neural P systems, shortly called SN P systems, are a class of distributed and parallel neural-like computing models, inspired from the way of neurons spiking and communicating with each other by means of spikes. In this work, we propose a new variant of SN P systems, called SN P systems with request rules. In such a system, besides spiking and forgetting rules, a neuron can have request rules, with which the neuron can sense "stimulus" from the environment by receiving a certain number of spikes. We investigate the computation power of SN P systems with request rules. It is obtained that such systems are Turing universal, even with a small number of neurons. Specifically, (i) SN P systems with request rules having 4 neurons can compute any set of Turing computable natural numbers and (ii) with 47 neurons such systems can compute any Turing computable function.

With mathematical motivation, we consider a combination of basic features of multiset-rewriting P systems and of spiking neural P systems, that is, we consider cell-like P systems with spiking rules in their membranes (hence dealing with only one kind of objects, the spikes). The universality of these systems as number generating devices is proved for the two usual ways to define the output (internally or externally) and for various restrictions on the spiking rules. Several research topics are also pointed out.

In spite of the fact that many ways of using the evolution rules in a P system were already investigated, there is still a case, which we call the flat maximal parallelism, which appeared in several papers, but which deserves a more careful attention: in each step, in each membrane, a maximal set of applicable rules is chosen and each rule in the set is applied exactly once. In this work, flat maximal parallelism is studied for non-cooperating P systems with promoters. Specifically, we prove that non-cooperating P systems with at most one promoter associated with any rule, working in the flat maximally parallel way, are Turing universal (the Turing universality of such P systems is open if they work in the maximally parallel way). Moreover, a uniform solution to the SAT problem is provided by using non-cooperating P systems with promoters and membrane division, working in the flat maximal parallel way.

A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed "colored" and in each step only rules of the same "color" are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode.

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired by spiking neurons. SN P systems with anti-spikes (ASN P systems) are a variant of SN P systems, which were inspired by inhibitory impulses/spikes or inhibitory synapses. In this work, we consider ASN P systems with the restrictions: (1) systems are simple in the sense that each neuron has only one rule; (2) at each step the neuron(s) with the maximum number of spikes among the neurons that are active (can spike) will fire; (3) the feature of delays and forgetting rules are not used. These restrictions make the systems working in a sequential way. We investigate the computational power of ASN P systems under these restrictions. Specifically, we prove that such systems with spiking rules of categories ( a , a ) and ( a , a ? ) are universal as both number generating and accepting devices. We also prove that ASN P systems with inhibitory synapses using spiking rules of category ( a , a ) are universal as both generating and accepting devices. These results show that ASN P systems are still powerful working with these restrictions.

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons process information and communicate by means of spikes, where neurons are different in the sense that they can have different sets of spiking rules. In this work, we consider a variant of SN P systems with two restrictions: (1) all neurons contain only spikes (neurons are homogeneous in this case, since they can be considered as containers of spikes), while the spiking rules are moved on the synapses; (2) all synapses are homogeneous in the sense that each synapse has the same set of rules. These restrictions correspond to the fact that the SN P system consists of only one kind of neurons and one kind of synapses. The computational power of SN P systems with homogeneous neurons and synapses is investigated. Specifically, it is proved that such systems are Turing universal as both number generating and number accepting devices.

The robustness in real-world complex systems with dependency connectivities differs from that in isolated networks. Although most complex network research has focused on interdependent undirected systems, many real-world networks---such as gene regulatory networks and traffic networks---are directed. We thus develop an analytical framework for examining the robustness of networks made up of directed networks of differing topologies. We use it to predict the phase transitions that occur during node failures and to generate the phase diagrams of a number of different systems, including treelike and random regular (RR) networks of directed Erd\ifmmode \mbox{\H{o}}\else \H{o}\fi{}s-R\'enyi (ER) networks and scale-free networks. We find that the the phase transition and phase diagram of networks of directed networks differ from those of networks of undirected networks. For example, the RR networks of directed ER networks show a hybrid phase transition that does not occur in networks of undirected ER networks. In addition, system robustness is affected by network topology in networks of directed networks. As coupling strength $q$ increases, treelike networks of directed ER networks change from a second-order phase transition to a first-order phase transition, and RR networks of directed ER networks change from a second-order phase transition to a hybrid phase transition, then to a first-order phase transition, and finally to a region of collapse. We also find that heterogenous network systems are more robust than homogeneous network systems. We note that there are multiple phase transitions and triple points in the phase diagram of RR networks of directed networks and this helps us understand how to increase network robustness when designing interdependent infrastructure systems.

The catalytic DNA circuits play a critical role in engineered biological systems and molecular information processing. Actually, some of the natural or synthetic DNA circuits were triggered by covalent modifications, where conformational changes were induced to facilitate complex DNA engineering functions and signal transmissions. However, most of the reported artificial catalytic DNA circuits were regulated by the toehold-mediated reaction. Therefore, it is significant to propose a strategy to regulate the catalytic DNA circuit not only by the toehold-mediated mechanism, but also by involving the conformational changes induced by the covalent modification. In this study, we developed the catalytic DNA logic circuits regulated by DNAzyme. Here, a regulation strategy based on the covalent modification was proposed to control the DNA circuit, combing two reaction mechanisms: DNAzyme digestion and entropy-driven strand displacement. The DNAzyme and DNA catalyst can participate into the reactions alternatively, thus realizing the cascading catalytic circuits. Using the DNAzyme regulation, a series of logic gates (YES, OR and AND) were constructed. In addition, a two-layer cascading circuit and a feedback self-catalysis circuit were also established. The proposed DNAzyme-regulated strategy shows great potentials as a reliable and feasible method for constructing more complex catalytic DNA circuits.

A variety of two-dimensional array grammar models generating picture array languages have been introduced and investigated, utilizing and extending the well-established notions and techniques of formal string language theory. On the other hand the versatile computing model with a generic name of P system in the area of membrane computing, has turned out to be a rich framework for different kinds of problems in a variety of fields. Picture array generation in the field of two-dimensional (2D) languages is one such area where P systems with array objects and array rewriting, referred to as array P systems, have been fruitfully employed in increasing the generating power of the 2D grammar models. A variety of array P systems have been proposed in the literature. The objective of this survey is to review and describe the salient features of the major types of array P systems, which have served as the basis for developing other kinds of array P systems. Applications of these array P systems are also briefly described besides indicating possible new directions of investigation.

Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class P can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (n,1), for each natural number n≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem.

Matrix insertion-deletion systems are a class of insertion-deletion systems, where insertion and deletion rules are grouped in sequences, and it is known that such systems with two symbols context-free insertion and deletion rules are not computationally complete. In this work, matrix insertion-deletion systems with exo-operations (MIDEs, in short) are proposed, where insertion and deletion operations are applied only at the ends of a string (called exo-operations). The computation power of context-free MIDEs as language generators is investigated. We prove that context-free MIDEs of matrices size two with one symbol insertion and two symbols deletion are computationally complete, and so are systems with two symbols insertion and one symbol deletion. Moreover, if the size of matrices is three, the computational completeness can also be reached by context-free MIDEs with one symbol insertion and one symbol deletion. These results show that the computational power of MIDEs is strictly increased by introducing the exo-operations of insertion and deletion.

We aim to compare functionality of symport/antiport with embedded rewriting to that of symport/antiport accompanied by rewriting, by two-way simulation, in case of tissue P systems with parallel communication. A simulation in both directions with constant slowdown is constructed.

Tissue P systems are computational models inspired by the way of biochemical substance movement/exchange between two cells or between a cell and the environment, where all communication (symport/antiport) rules used in a system are initially set up and keep unchanged during any computation. In this work, a variant of tissue P systems, called tissue P systems with rule production/removal (abbreviated as TRPR P systems) is considered, where rules in a system are dynamically changed during a computation, that is, at any computation step new rules can be produced and some existing rules can be removed. The computation power of TRPR P systems is investigated. It is proved that Turing universality is achieved for TRPR P systems with one cell, and using symport rules of length at most 1, antiport rules of length at most 2 or symport rules of length at most 2 and working in a maximally parallel manner. We further show that TRPR P systems with two cells, using symport rules of length at most 1, and working in a flat maximally parallel manner, are Turing universal.

Tissue P systems are a class of bio-inspired computing models motivated by biochemical interactions between cells in a tissue-like arrangement. Tissue P systems with cell division offer a theoretical device to generate an exponentially growing structure in order to solve computationally hard problems efficiently with the assumption that there exists a global clock to mark the time for the system, the execution of each rule is completed in exactly one time unit. Actually, the execution time of different biochemical reactions in cells depends on many uncertain factors. In this work, with this biological inspiration, we remove the restriction on the execution time of each rule, and the computational efficiency of tissue P systems with cell division is investigated. Specifically, we solve subset sum problem by tissue P systems with cell division in a time-free manner in the sense that the correctness of the solution to the problem does not depend on the execution time of the involved rules.

Cell-like spiking neural (cSN) P systems are a class of distributed and parallel computation models inspired by both the way in which neurons process information and communicate to each other by means of spikes and the compartmentalized structures of living cells. cSN P systems have been proved to be Turing universal if more spikes can be produced by consuming some spikes or spikes can be replicated. In this paper, in order to answer the open problem whether this functioning of producing more spikes and replicating spikes can be avoided by using some strategy without the loss of computation power, we introduce cSN P systems with request rules, which have classical spiking rules and forgetting rules, and also request rules in the skin membrane. The skin membrane can receive spikes from the environment by the application of request rules. cSN P systems with request rules are proved to be Turing universal. The results show that the decrease of computation power caused by removing the internal functioning of producing more spikes and replicating spikes can be compensated by request rules, which suggests that the communication between a cell and the environment is an essential ingredient of systems in terms of computation power.

Spiking neural P (SN P) systems are a class of parallel computation models inspired by neurons, where the firing condition of a neuron is described by a regular expression associated with spiking rules. However, it is NP-complete to decide whether the number of spikes is in the length set of the language associated with the regular expression. In this paper, in order to avoid using regular expressions, two major and rather natural modifications in their form and functioning are proposed: the spiking rules no longer check the number of spikes in a neuron, but, in exchange, a polarization is associated with neurons and rules, one of the three electrical charges −, 0,+. Surprisingly enough, the computing devices obtained are still computationally complete, which are able to compute all Turing computable sets of natural numbers. On this basis, the number of neurons in a universal SN P system with polarizations is estimated. Several research directions are mentioned at the end of this paper.

When controlling a complex networked system it is not feasible to control the full network because many networks, including biological, technological, and social systems, are massive in size and complexity. But neither is it necessary to control the full network. In complex networks, the giant connected components provide the essential information about the entire system. How to control these giant connected components of a network remains an open question. We derive the mathematical expression of the degree distributions for four types of giant connected components and develop an analytic tool for studying the controllability of these giant connected components. We find that for both Erdős-Rényi (ER) networks and scale-free (SF) networks with p fraction of remaining nodes, the minimum driver node density to control the giant component first increases and then decreases as p increases from zero to one, showing a peak at a critical point p=p_{m}. We find that, for ER networks, the peak value of the driver node density remains the same regardless of its average degree 〈k〉 and that it is determined by p_{m}〈k〉. In addition, we find that for SF networks the minimum driver node densities needed to control the giant components of networks decrease as the degree distribution exponents increase. Comparing the controllability of the giant components of ER networks and SF networks, we find that when the fraction of remaining nodes p is low, the giant in-connected, out-connected, and strong-connected components in ER networks have lower controllability than those in SF networks.

Labelled splicing P systems are distributed parallel computing models, where sets of strings that evolve by splicing rules are labelled. In this work, we consider labelled splicing systems with the following modifications: (i) The strings in the membranes are present in arbitrary number of copies; (ii) the rules in the regions are finite in number. Results on the language family generated by the labelled splicing system in comparison with the language families of the Chomsky hierarchy, including recursively enumerable languages, are obtained, by involving only either one or two membranes in the P systems considered.

Rewriting P systems, as language generating devices, are one of the earliest classes of P systems with structured strings as objects and the rewriting rules as evolution rules. Flat splicing is an operation on strings, inspired by a splicing operation on circular strings. In this work, we consider a variant of rewriting P systems with only regular or linear rewriting rules and alphabetic flat splicing rules, and the language generative power of rewriting P systems with flat splicing rules in comparison with flat splicing systems and Chomsky hierarchy is investigated.

In this study, an aptamer-substrate strategy is introduced to control programmable DNA origami pattern. Combined with DNA aptamer-substrate binding and DNAzyme-cutting, small DNA tiles were specifically controlled to fill into the predesigned DNA origami frame. Here, a set of DNA logic gates (OR, YES, and AND) are performed in response to the stimuli of adenosine triphosphate (ATP) and cocaine. The experimental results are confirmed by AFM imaging and time-dependent fluorescence changes, demonstrating that the geometric patterns are regulated in a controllable and programmable manner. Our approach provides a new platform for engineering programmable origami nanopatterns and constructing complex DNA nanodevices.

issue P systems with channel states are a class of bio-inspired parallel computational models, where rules are used in a sequential manner (on each channel, at most one rule can be used at each step). In this work, tissue P systems with channel states working in a flat maximally parallel way are considered, where at each step, on each channel, a maximal set of applicable rules that pass from a given state to a unique next state, is chosen and each rule in the set is applied once. The computational power of such P systems is investigated. Specifically, it is proved that tissue P systems with channel states and antiport rules of length two are able to compute Parikh sets of finite languages, and such P systems with one cell and noncooperative symport rules can compute at least all Parikh sets of matrix languages. Some Turing universality results are also provided. Moreover, the NP-complete problem SAT is solved by tissue P systems with channel states, cell division and noncooperative symport rules working in the flat maximally parallel way; nevertheless, if channel states are not used, then such P systems working in the flat maximally parallel way can solve only tractable problems. These results show that channel states provide a frontier of tractability between efficiency and non-efficiency in the framework of tissue P systems with cell division (assuming P ≠ NP). Ministerio de Economía y Competitividad TIN2012-37434

Tissue P systems are a class of distributed parallel computing devices inspired by biochemical interactions between cells in a tissue-like arrangement, where objects can be exchanged by means of communication channels. In this work, inspired by the biological facts that the movement of most objects through communication channels is controlled by proteins and proteins can move through lipid bilayers between cells (if these cells are fused), we present a new class of variant tissue P systems, called tissue P systems with protein on cells, where multisets of objects (maybe empty), together with proteins between cells are exchanged. The computational power of such P systems is studied. Specifically, an efficient (uniform) solution to the SAT problem by using such P systems with cell division is presented. We also prove that any Turing computable set of numbers can be generated by a tissue P system with protein on cells. Both of these two results are obtained by such P systems with communication rules of length at most 4 (the length of a communication rule is the total number of objects and proteins involved in that rule). Ministerio de Economía y Competitividad TIN2012-37434

Membrane fission is a process by which a biological membrane is split into two new ones in the manner that the content of the initial membrane is separated and distributed between the new membranes. Inspired by this biological phenomenon, membrane separation rules were considered in membrane computing. In this work, we investigate cell-like P systems with symport/antiport rules and membrane separation rules from a computational complexity perspective. Specifically, we establish a limit on the efficiency of such P systems which use communication rules of length at most two, and we prove the computational efficiency of this kind of models when using communication rules of length at most three. Hence, a sharp borderline between tractability and NP–hardness is provided in terms of the length of communication rules. Ministerio de Economía y Competitividad TIN2012-37434

The notion of time-free solution to decision problem by P systems with proteins on membranes, in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, is defined.A time-free uniform solution to the SAT problem by P systems with proteins on membranes is given. P systems with proteins on membranes are a class of bio-inspired computing models, where the execution of each rule completes in exactly one time unit. However, in living cells, the execution time of biochemical reactions is difficult to know precisely because of various uncontrollable factors. In this work, we present a time-free uniform solution to SAT problem by P systems with proteins on membranes in the sense that the correctness of the solution is irrelevant to the times associated with the involved rules, and the P systems are constructed from the sizes of instances.

Cell-like P systems with symport/antiport rules are inspired by the structure of a cell and the way of communicating substances through membrane channels between neighboring regions. In this work, channel states are introduced into cell-like P systems with symport/antiport rules, and we call this variant of communication P systems as cell-like P systems with channel states and symport/antiport rules. In such P systems, at most one channel is established between neighboring regions, each channel associates with one state in order to control communication at each step, and rules are used in a sequential manner: on each channel at most one rule can be used at each step. The computational power of such P systems is investigated. Specifically, we show that cell-like P systems with two states and using uniport rules, or with any number of states and using antiport rules of length two, are able to compute only finite sets of non-negative integers.We further prove that cell-like P systems with two membranes are as powerful as Turing machines when channel states and symport/antiport rules are suitably combined. The results show that channel states are a feature that can increase the computational power of cell-like P systems with symport/antiport rules. Ministerio de Economía y Competitividad TIN2012-37434