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.

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 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 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)

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.

Maximally parallel manner is a usual rule application strategy for P systems, where rules should be used in parallel to the maximum degree possible. In this work, we consider a rule application strategy, rule synchronization, where some synchronization sets of rules are given, a rule in a synchronization set of rules can be applied only if all rules in the set are enabled. Tissue P systems with synchronized symport/antiport rules and synchronization sets of rules are called tissue P systems with synchronized symport/antiport rules. We prove that tissue P systems with synchronized symport/antiport rules consisting of only one cell are universal. Besides, we prove that the SAT problem can be solved by the proposed tissue P systems when cell division rules are introduced. The results show that synchronization over rules is a rule application strategy that can increase the computational power of tissue P systems with symport/antiport rules.

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.

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.

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

Spiking neural P systems with rules on synapses are a new variant of spiking neural P systems. In the systems, the neuron contains only spikes, while the spiking/forgetting rules are moved on the synapses. It was obtained that such system with 30 neurons (using extended spiking rules) or with 39 neurons (using standard spiking rules) is Turing universal. In this work, this number is improved to 6. Specifically, we construct a Turing universal spiking neural P system with rules on synapses having 6 neurons, which can generate any set of Turing computable natural numbers. As well, it is obtained that spiking neural P system with rules on synapses having less than two neurons are not Turing universal: i) such systems having one neuron can characterize the family of finite sets of natural numbers; ii) the family of sets of numbers generated by the systems having two neurons is included in the family of semi-linear sets of natural numbers.

Axon P systems are computing models with a linear structure in the sense that all nodes (i.e., computing units) are arranged one by one along the axon. Such models have a good biological motivation: an axon in a nervous system is a complex information processor of impulse signals. Because the structure of axon P systems is linear, the computational power of such systems has been proved to be greatly restricted; in particular, axon P systems are not universal as language generators. It remains open whether axon P systems are universal as number generators. In this paper, we prove that axon P systems are universal as both number generators and function computing devices, and investigate the number of nodes needed to construct a universal axon P system. It is proved that four nodes (respectively, nine nodes) are enough for axon P systems to achieve universality as number generators (respectively, function computing devices). These results illustrate that the simple linear structure is enough for axon P systems to achieve a desired computational power.

Surrogate-assisted evolutionary algorithms have been developed mainly for solving expensive optimization problems where only a small number of real fitness evaluations are allowed. Most existing surrogate-assisted evolutionary algorithms are designed for solving low-dimensional single or multiobjective optimization problems, which are not well suited for many-objective optimization. This paper proposes a surrogateassisted many-objective evolutionary algorithm that uses an artificial neural network to predict the dominance relationship between candidate solutions and reference solutions instead of approximating the objective values separately. The uncertainty information in prediction is taken into account together with the dominance relationship to select promising solutions to be evaluated using the real objective functions. Our simulation results demonstrate that the proposed algorithm outperforms the state-of-the-art evolutionary algorithms on a set of manyobjective optimization test problems.

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.

Spiking neural P systems, namely SN P systems, are a class of distributed and parallel neural-like computation models, inspired from the way neurons communicate by means of spikes. It has been shown that SN P systems have powerful computation capability and significant potential in real-life applications, and they have received more and more attraction from the scientific community. This paper firstly introduces the formal definition of standard SN P systems and some notions which are often used in this field. Then, the theoretical results about the computation power and efficiency of SN P systems are surveyed. The applications of SN P systems are recalled by summarizing the literature about the real-life applications of SN P systems. Finally, some hot topics and further research lines on SN P systems are provided.

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

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.

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 from the way neurons communicate by means of spikes. Asynchronous SN P systems are non-synchronized systems, where the use of spiking rules (even if they are enabled by the contents of neurons) is not obligatory. It remains open whether asynchronous SN P systems with standard spiking rules are equivalent with Turing machines. In this paper, with a biological inspiration (in order to achieve some specific biological functioning, neurons from the same functioning motif or community work synchronously to cooperate with each other), we introduce the notion of local synchronization into asynchronous SN P systems. The computation power of asynchronous SN P systems with local synchronization is investigated. Such systems consisting of general neurons (respectively, unbounded neurons) and using standard spiking rules are proved to be universal. Asynchronous SN P systems with local synchronization consisting of bounded neurons and using standard spiking rules characterize the semilinear sets of natural numbers. These results show that the local synchronization is useful, it provides some ''programming capacity'' useful for achieving a desired computation power.

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

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.

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.

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.