Search

Tissue P systems with evolutional symport/antiport rules are a variant of tissue P systems, where objects are communicated through regions by symport/antiport rules, and objects may evolve during this process. It is known that such systems are able to solve NP problems in a polynomial time (and exponential space), when cell division is allowed. In this work, we continue to investigate the computational complexity aspects for tissue P systems with evolutional symport/antiport rules. We prove that problems beyond NP can also be solved. In particular, we show that deterministic systems of this type are able to solve all problems in the complexity class PP. Moreover, if non-deterministic systems are considered, then all problems in the class PSPACE can be solved.

In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important task to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumed efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects; that is, with recognizer P systems from $${\mathcal {TSEC}}(2, 2)$$ TSEC ( 2 , 2 ) . This result improves a previous one, when 3 objects could be used in the left-hand side of the evolutional communication rules

Spiking neural P systems (SN P systems) refer to a type of distributed parallel neural computation model in the membrane computing framework. In this work, a new type of SN P system is examined, i.e., spiking neural P systems with polarizations (PSN P systems), by taking inspiration from the polarized cell membrane of a neuron. For the PSN P system, the firing condition of rules is the neuron-associated polarization. This work focuses on examining the computation power of the PSN P systems adopting the sequential mode induced by the minimum spike number, where at a computation step, one (resp., all) of neurons that hold the minimum spike number within the neurons which can fire will fire, i.e., the min-sequentiality strategy (resp., min-pseudo-sequentiality strategy). We prove that PSN P systems adopting the min-sequentiality strategy or min-pseudo-sequentiality strategy are Turing universal as the number generating devices. These results indicate the computation power of PSN P systems is robust regarding their strategies of sequentiality.

Cell-like P systems where communication between the regions are carried out by rules of type symport/antiport are considered. These systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. The environment plays an active role in the sense that it not only can receive objects from the system, but also send objects into it. There is an alphabet associated with the environment whose elements appear in an arbitrary large number of copies at the initial configuration. This property seems too strong from a complexity view, but it has been widely exploited in the design of efficient solutions to computationally hard problems when some mechanisms (inspired by mitosis and membrane fission) allowing to construct an exponential workspace in linear time, are considered. In this paper, complexity aspects of P systems with symport/antiport rules and membrane division are considered when the set associated with the environment is the emptyset. It is shown that the role of the environment is irrelevant for such kind of P systems, in contrast with the well known results concerning to its relevance when membrane separation is used instead of membrane division.

Spiking neural P systems (SN P systems) are a class of distributed and parallel neural-like computing models, inspired from the way neurons communicate by means of spikes. In this paper, a new variant of the systems, called SN P systems with learning functions, is introduced. Such systems can dynamically strengthen and weaken connections among neurons during the computation. A class of specific SN P systems with simple Hebbian learning function is constructed to recognize English letters. The experimental results show that the SN P systems achieve average accuracy rate 98.76% in the test case without noise. In the test cases with low, medium, and high noises, the SN P systems outperform back propagation neural networks and probabilistic neural networks. Moreover, comparing with spiking neural networks, SN P systems perform a little better in recognizing letters with noise. The result of this paper is promising in terms of the fact that it is the first attempt to use SN P systems in pattern recognition after many theoretical advancements of SN P systems, and SN P systems exhibit the feasibility for tackling pattern recognition problems.

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

Asynchronous tissue P systems with symport/antiport rules are a class of parallel computing models inspired by cell tissue working in a non-synchronized way, where the use of rules is not obligatory, that is, at a computation step, an enabled rule may or may not be applied. In this work, the notion of local synchronization is introduced at three levels: rules, channels, and cells. If a rule in a locally synchronous set of rules (resp., cells or channels) is used, then all enabled rules in the same locally synchronous set of rules (resp., whose involved channels or cells) should be applied in a maximally parallel manner and the implementation of these rules is finished in one computation step. The computational power of local synchronization on asynchronous tissue P systems with symport/antiport rules at the three levels is investigated. It is shown that asynchronous tissue P systems with symport/antiport rules and with locally synchronous sets of rules, channels, or cells are all Turing universal. By comparing the computational power of asynchronous tissue P systems with or without local synchronization, it can be found that the local synchronization is a useful tool to achieve a desired computational power.

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 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 (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.

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 through spikes, where the integrate-and-fire behavior of neurons and the distribution of produced spikes are achieved by spiking rules. In this work, a novel mechanism for separately describing the integrate-and-fire behavior of neurons and the distribution of produced spikes, and a novel variant of the SNP systems, named evolution-communication SNP (ECSNP) systems, is proposed. More precisely, the integrate-and-fire behavior of neurons is achieved by spike-evolution rules, and the distribution of produced spikes is achieved by spike-communication rules. Then, the computational power of ECSNP systems is examined. It is demonstrated that ECSNP systems are Turing universal as number-generating devices. Furthermore, the computational power of ECSNP systems with a restricted form, i.e. the quantity of spikes in each neuron throughout a computation does not exceed some constant, is also investigated, and it is shown that such restricted ECSNP systems can only characterize the family of semilinear number sets. These results manifest that the capacity of neurons for information storage (i.e. the quantity of spikes) has a critical impact on the ECSNP systems to achieve a desired computational power.

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.

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.

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.

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.

Spiking Neural [Formula: see text] Systems are Neural System models characterized by the fact that each neuron mimics a biological cell and the communication between neurons is based on spikes. In the Spiking Neural [Formula: see text] systems investigated so far, the application of evolution rules depends on the contents of a neuron (checked by means of a regular expression). In these [Formula: see text] systems, a specified number of spikes are consumed and a specified number of spikes are produced, and then sent to each of the neurons linked by a synapse to the evolving neuron. [Formula: see text]In the present work, a novel communication strategy among neurons of Spiking Neural [Formula: see text] Systems is proposed. In the resulting models, called Spiking Neural [Formula: see text] Systems with Communication on Request, the spikes are requested from neighboring neurons, depending on the contents of the neuron (still checked by means of a regular expression). Unlike the traditional Spiking Neural [Formula: see text] systems, no spikes are consumed or created: the spikes are only moved along synapses and replicated (when two or more neurons request the contents of the same neuron). [Formula: see text]The Spiking Neural [Formula: see text] Systems with Communication on Request are proved to be computationally universal, that is, equivalent with Turing machines as long as two types of spikes are used. Following this work, further research questions are listed to be open problems.

Inspired by mitosis process and membrane fission processes, cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules have been introduced, respectively. These computation systems have two key features: the ability to have infinite copies of some objects (within an active environment) and to generate an exponential workspace in polynomial time. In this work, we extend the P-Lingua framework for simulating that kind of P systems taking into account these two features. Consequently, a new simulator has been developed and included in pLinguaCore library. The functioning of the simulator has been checked by simulating efficient solutions to SAT problem using a family of cell-like P systems with symport/antiport rules and membrane division rules or membrane separation rules. The corresponding MeCoSim based application is also provided. ∗Address for correspondence: Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. Received February 2015; revised April 2015. 212 L.F. Macias-Ramos et al. / P–Lingua Simulator for P Systems with Symport/Antiport Rules

P systems are a class of computational models inspired by the structure and the functioning of a living cell. In the semantics of P systems, there exists a global clock, which marks the time for the system, and the execution time of each rule takes exactly one time unit. However, in living cells, the execution time of different biochemical reactions is dependent on many uncontrollable factors, and it is hard to know precisely the specific execution time of a reaction. In this work, with this biological inspiration, we consider the class of P systems with active membranes that are "robust" against the execution time of rules. Specifically, we give a time-free uniform solution to the SAT problem using P systems with active membranes, where the constructed P system can solve a family of instances with an arbitrarily given size, and the execution time of the involved rules has no influence on the correctness of the solution. We also prove that any Turing computable set of numbers can be generated by a time-free P system with active membranes in the sense that the set of numbers generated by the given P system with active membranes does not depend on the execution time of rules.

Spiking neural P systems (SN P systems for short) are a class of neural-like computing models in the framework of membrane computing. Inspired by the neurophysiological structure of the brain, SN P systems have been extended in various ways. P–Lingua is a standard language for the definition of P systems, where pLinguaCore library provides particular implementations of parsers and simulators for the models specified in P–Lingua. A support for simulating SN P systems in P–Lingua was introduced recently and soon expanded to cover further features of these systems. In this paper, we present an extension of P–Lingua related to asynchronous SN P systems, in order to incorporate simulation capabilities for limited asynchronous SN P systems and asynchronous SN P systems with local synchronization.

P systems are a class of distributed and parallel computing models inspired by the structure and the functioning of a single cell and complexes of cells. The computational efficiency of P systems with active membranes has been investigated widely with the assumption that the application of rules is completed in exactly one time unit. However, in biological facts, different biological processes may take different times to complete, and the execution time of certain biological process could vary because of external uncontrollable conditions. With this biological motivation, in this work, we solve SAT problem by a family of P systems with active membranes in a time-free manner in the sense that the correctness of the solution does not depend on the precise timing of the involved rules. In such a solution, standard cell division rules for elementary membranes are applied: the newly generated membranes have the same label with their parent membrane. This result answers an open problem formulated in Song et al. (Theor Comput Sci 529:61---68, 2014).

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.

National Natural Science Foundation of China [61202011, 61272152, 61033003, 91130034, 61320106005]; Ph.D. Programs Foundation of Ministry of Education of China [20120121120039, 20120142130008]; Natural Science Foundation of Hubei Province [2011CDA027]

Tissue P systems are a class of distributed and parallel models of computation inspired by the way of communication among living cells or between cells and their environment. In this work, we investigate the computational power of tissue P systems, where each rule is assigned either with a label chosen from an alphabet or with the empty label λ . The sequence of labels of rules applied during a halting computation is defined as the result of the computation, and the set of all results computed by a given tissue P system is called a control language. We prove that tissue P systems with antiport rules of weight one and without symport rules characterize regular languages; tissue P systems with antiport rules of weight at most two (resp., symport rules of weight at most two) without symport rules (resp., antiport rules) are universal. Tissue P systems with antiport rules of weight one and symport rules of weight one are also proved to be universal. These results show that the rule complexity is crucial for tissue P systems to achieve a desired computational power.

Spiking neural P systems (SN P systems, for short) are a class of membrane systems inspired from the way the neurons process information and communicate by means of spikes. In this paper, we introduce and investigate a new class of SN P systems, with spiking rules placed on synapses. The computational completeness is first proved, then two small universal SN P systems with rules on synapses for computing functions are constructed. Specifically, when using standard spiking rules, we obtain a universal system with 39 neurons, while when using extended spiking rules on synapses, a universal SN P system with 30 neurons is constructed.

P systems are a class of distributed and parallel computation models inspired by the structure and the functioning of living cells. P systems have been used to solve computation hard problems, where the execution of each rule is completed in unit time (a global clock is assumed for timing and synchronizing the execution of rules). The assumption that the execution of each rule takes exactly one time unit plays an vital role to make a system working synchronously, and it has also been used to characterize the computational efficiency and time complexity of a system. In this work, we investigate the computation power of P systems without such time assumption. Specifically, we give a time-free solution to SAT problem using P systems with active membranes in the sense that the correctness of the solution does not depend on the precise timing of the involved rules.

The biologically inspired model, known as P system, has proved to be a general framework for investigating several problems related to computing in different fields. Two-dimensional picture array languages is one such area in which different kinds of P systems have been constructed for picture array generation. Incorporating the feature of permitting symbols in the rules, a new variety of array P system is constructed here for generating picture languages consisting of picture arrays. The advantage of this approach is that there is a reduction in the number of membranes used in the construction, in comparison to the existing array P system models.

Spiking neural P systems (SN P systems, for short) with rules on synapses are a new variant of SN P systems, where the spiking and forgetting rules are placed on synapses instead of in neurons. Recent studies illustrated that this variant of SN P systems is universal working in the way that the synapses starting from the same neuron work in parallel (i.e., all synapses starting from the same neuron should apply their rules if they have rules to be applied). In this work, we consider SN P systems with rules on synapses working in another way: the synapses starting from the same neuron are restricted to work in a sequential way (i.e., at each step at most one synapse starting from the same neuron applies its rule). It is proved that the computational power of SN P systems with rules on synapses working in this way is reduced; specifically, they can only generate finite sets of numbers. Such SN P systems with rules on synapses are proved to be universal, if synapses are allowed to have weight at most 2 (if a rule which can generate n spikes is applied on a synapse with weight k, then the neuron linking to this synapse will receive totally nk spikes). Two small universal SN P systems with rules on synapses for computing functions are also constructed: a universal system with 26 neurons when using extended rules and each synapse having weight at most 2, and a universal system with 26 neurons when using standard rules and each synapse having weight at most 12. These results illustrate that the weight is an important feature for the computational power of SN P systems.

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. Each neuron can have several spiking rules and forgetting rules and neurons work in parallel in the sense that each neuron that can fire should fire at each computation step. In this work, we consider SN P systems working in the sequential way, where the sequentiality is induced by the minimum number of spikes: at each step, one (resp. all) of the neurons with the minimum number of spikes among the neurons that are active (can fire) will fire, called min-sequentiality (resp. min-pseudo-sequentiality). We prove that SN P systems working in min-sequentiality or min-pseudo-sequentiality are universal as both number generating and accepting devices, where the computation results are encoded by the time elapsed between the first two spikes of the output neuron. The results give positive answers to two open problems formulated in [O.H. Ibarra, A. Paun, A. Rodriguez-Paton, Sequential SNP systems based on min/max spike number, Theoretical Computer Science 410 (30-32) (2009) 2982-2991].

Splicing P systems are a class of distributed parallel computing models in the framework of membrane computing, which are inspired by the recombination of DNA molecules under the influence of restriction enzymes. In this work, a variant of P machine, called splicing P machine, is presented, which can provide an automata approach to investigate splicing P systems. It is shown that such a device can do what the splicing P system does. Several examples are given to illustrate that splicing P machine can provide the same results as the corresponding splicing P system. This work provides an answer to an open problem formulated by G. Ciobaun and M. Gontineac.

Spiking neural P systems SN P systems, for short are a class of distributed parallel computing devices inspired by the way neurons communicate by means of spikes, where neurons work in parallel in the sense that each neuron that can fire should fire at each computation step, and neurons can be different in the sense that they can have different sets of spiking rules. In this work, we consider SN P systems with the restrictions: 1 all neurons are homogeneous in the sense that each neuron has the same set of rules; 2 at each step the neuron with the maximum number of spikes among the neurons that are active can spike will fire. These restrictions correspond to the fact that the system consists of only one kind of neurons and a global view of the whole network makes the system sequential. The computation power of homogeneous SN P systems working in the sequential mode induced by the maximum spike number is investigated. Specifically, it is proved that such systems are universal as both generating and accepting devices.

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

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

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes, where neurons work in parallel in the sense that each neuron that can fire should fire, but the work in each neuron is sequential in the sense that at most one rule can be applied at each computation step. In this work, we consider SN P systems with the restriction that at most one neuron can fire at each step, and each neuron works in an exhaustive manner (a kind of local parallelism – an applicable rule in a neuron is used as many times as possible). Such SN P systems are called sequential SN P systems with exhaustive use of rules. The computation power of sequential SN P systems with exhaustive use of rules is investigated. Specifically, characterizations of Turing computability and of semilinear sets of numbers are obtained, as well as a strict superclass of semilinear sets is generated. The results show that the computation power of sequential SN P systems with exhaustive use of rules is closely related with the types of spiking rules in neurons.

Spiking neural P systems are a class of distributed parallel computing models inspired from the way neurons communicate with each other by means of electrical impulses, where there is a synapse between each pair of connected neurons. However, in a biological system, there can be several synapses for each pair of connected neurons. In this study, inspired by this biological observation, synapses in a spiking neural P system are endowed with integer weight denoting the number of synapses for each pair of connected neurons. With the price of weight on synapses, quite small universal spiking neural P systems can be constructed. Specifically, a universal spiking neural P system with standard rules and weight having 38 neurons is produced as device of computing functions; as generator of sets of numbers, we find a universal system with standard rules and weight having 36 neurons.

Spiking neural P systems are a class of distributed and parallel computing models inspired by spiking neurons. In this work, the features of neuron division and neuron budding are introduced into the framework of spiking neural P systems, which are processes inspired by neural stem cell division. With neuron division and neuron budding, a spiking neural P system can generate exponential work space in polynomial time as the case for P systems with active membranes. In this way, spiking neural P systems can efficiently solve computationally hard problems by means of a space-time tradeoff, which is illustrated with an efficient solution to SAT problem.

Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with cell separation is constructed for efficiently solving a well-known NP-complete problem, the partition problem.

In a biological system, if a long enough time interval is given, an enabled chemical reaction will finish its reaction in the given time interval. With this motivation, it is natural to impose a bound on the time interval when an enabled spiking rule in a spiking neural P system (SN P system, for short) remains unused. In this work, a new working mode of SN P systems is defined, which is called limited asynchronous mode. In an SN P system working in limited asynchronous mode, if a rule is enabled at some step, this rule is not obligatorily used. From this step on, if the unused rule may be used later, it should be used in the given time interval. If further spikes make the rule non-applicable, then the computation continues in the new circumstances. The computation result of a computation in an SN P system working in limited asynchronous mode is defined as the total number of spikes sent into the environment by the system. It is proved that limited asynchronous SN P systems with standard spiking rules are universal. If the number of spikes present in each neuron of a limited asynchronous SN P system with standard spiking rules is bounded during a computation, then the power of a limited asynchronous SN P system with standard spiking rules falls drastically, and we get a characterization of semilinear sets of numbers.

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules Ministerio de Educación y Ciencia TIN2009-13192 Junta de Andalucía P08-TIC-04200

Looking for small universal computing devices is a natural and well investigated topic in computer science. Recently, this topic was also investigated in the framework of spiking neural P systems. One of the small universality results is that a small weakly universal extended spiking neural P system with 12 neurons was constructed. In this paper, a new way is introduced for simulating register machines by spiking neural P systems, where only one neuron is used for all instructions of the register machine; in this way, we can use less neurons to construct universal spiking neural P system. Specifically, we give a smaller weakly universal spiking neural P system that uses extended rules and has only 9 neurons.