Virus machines, which develop models of computation inspired by biological processes and the spread of viruses among hosts, deviate from the traditional methods. These virus machines are recognized for their computational power (functioning as algorithms) and their ability to tackle computationally difficult problems. In this paper, we introduce a new extension of the matrix-based representation of virus machines. In this way, hosts, the number of viruses and the instructions to control virus transmission are represented as vectors and matrices, describing the computations of virus machines by linear algebra operations. We also use our matrix representation to show invariants, useful in the proofs, of such machines. In addition, an explicit example is shown to clarify the computation and invariants using the representation. That is, a virus machine that computes the discrete logarithm, which relies on the presumed intractability of cryptosystems such the digital signature algorithm.

Abstract Virus machines are computing devices inspired by the transmission and replication of viruses. This model of computation has been proved to be as powerful as Turing machines, while using very simple semantics: instructions can open channels to let viruses travel between different hosts. The basic model is sequential, in the sense that only one instruction can be executed in each time step. This behaviour is, in principle, easy to follow by using pen and paper, but it can become harder when the model is big enough, as it happens with other models of computation. This paper introduces a base software for virus machines that simulates their behaviour and has an easy approach for both researchers and developers. Besides, apart from the simulator, the software has two other main purposes: on the one hand, a experimental validator has been introduced to help the researcher with both the design and the formal verification of such devices; on the other hand, it has included a tool to create a LaTeX graphic of a virus machine with the usual visuals.

Spiking Neural P Systems (SNP) are well-established computing models that take inspiration from spikes between biological neurons; these models have been widely used for both theoretical studies and practical applications. Virus machines (VMs) are an emerging computing paradigm inspired by viral transmission and replication. In this work, a novel extension of VMs inspired by SNPs is presented, called Virus Machines with Host Excitation (VMHEs). In addition, the universality and explicit results between SNPs and VMHEs are compared in both generating and computing mode. The VMHEs defined in this work are shown to be more efficient than SNPs, requiring fewer memory units (hosts in VMHEs and neurons in SNPs) in several tasks, such as a universal machine, which was constructed with 18 hosts less than the 84 neurons in SNPs, and less than other spiking models discussed in the work.

P systems are non-deterministic, parallel and distributed models of computation inspired by the behaviour and structure of living cells. Spiking neural P systems synthesise the connections that exist between neurons in the human brain, using pulses as a form of transmission of information. Usually, when a spiking neural P system is defined to solve any problem, it is checked in several cases to know if it works for them. But this methodology is not sufficient to verify if the system always works in a correct way. In this work, we introduce a methodology to look for characteristics in computations of spiking neural P systems that can be used to formally verify that the model works as it is intended.

Spiking neural P (SNP) systems are a class of distributed and parallel neural-like computing models that are inspired by the mechanism of spiking neurons and are 3rd-generation neural networks. Chaotic time series forecasting is one of the most challenging problems for machine learning models. To address this challenge, we first propose a nonlinear version of SNP systems, called nonlinear SNP systems with autapses (NSNP-AU systems). In addition to the nonlinear consumption and generation of spikes, the NSNP-AU systems have three nonlinear gate functions, which are related to the states and outputs of the neurons. Inspired by the spiking mechanisms of NSNP-AU systems, we develop a recurrent-type prediction model for chaotic time series, called the NSNP-AU model. As a new variant of recurrent neural networks (RNNs), the NSNP-AU model is implemented in a popular deep learning framework. Four datasets of chaotic time series are investigated using the proposed NSNP-AU model, five state-of-the-art models, and 28 baseline prediction models. The experimental results demonstrate the advantage of the proposed NSNP-AU model for chaotic time series forecasting.

Virus machines are computational devices inspired by the movement of viruses between hosts and their capacity to replicate using the resources of the hosts. This behavior is controlled by an external graph of instructions that opens different channels of the system to make viruses capable of moving. This model of computation has been demonstrated to be as powerful as turing machines by different methods: by generating Diophantine sets, by computing partial recursive functions and by simulating register machines. It is interesting to investigate the practical use cases of this model in terms of possibilities and efficiency. In this work, we give the basic modules to create an arithmetic calculator. As a practical application, two pairing functions are calculated by means of two different virus machines. Pairing functions are important resources in the field of cryptography. The functions calculated are the Cantor pairing function and the Gödel pairing function.

Abstract 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

Tissue-like P systems with channel states are a type of classical membrane systems in which objects transferred among regions are controlled by states placed in the channels between regions. However, an important biological fact is the existence of a “barrier” to the diffusion of signal molecules, which tend to remain confined to some particular micro-habitat. This feature allows quorum sensing to convey information about the physiological state of spatially separated sub-populations. Therefore, in this article, we design a novel class-variant of P systems namedtissue P systems with states in cells(TSIC P systems). Here, each cell contains one and only one state at any moment (the environment has no state), and objects transferred among regions are controlled by states (or a state) that are placed in the corresponding cells (or a cell). We discuss thecomputability theoryof TSIC P systems by showing that Turing universality is acquired by TSIC P systems, which are worked both in a flat maximal parallelism and in a maximal parallelism. In addition, when cell division is considered in TSIC P systems, then tissue P systems with states in cells and cell division (TSICD P systems) are constructed. The (presumed)computational efficiencyof TSICD P systems is reached by offering a uniform solution to the satisfiability problem.

Originally, in P systems the environment plays a passive role; that is, it can only receive objects, without having the ability to send objects to the system. Later, tissue P systems were introduced, where the cells are located in the environment in the sense that they can communicate between each other but also with the environment. In fact, a special alphabet was introduced as a way to symbolize the chemical elements available in it and that can interact with the cells. In the framework of membrane computing, all the objects of this alphabet are present in the environment with an arbitrary multiplicity at the beginning of the computation; that is, there are enough objects of this type in the environment to fire the rules that can be fired by these objects. From the computational complexity point of view, it seems to be a very strong ingredient, since it adds a virtually infinite number of objects to the system in the whole computation. In this paper, we demonstrate that the behaviour of this special alphabet can be simulated by a generation stage ruled by evolutional communication rules and/or division/separation rules, such that the ability of these systems to efficiently solve presumably hard problems is not changed if the environment does not play an active role.

Natural computing is a research area of computer science where different models of computation arise from the inspiration of real-life natural processes. In particular, virus machines are devices inspired by the transmission of viruses between different hosts, and how they replicate in the organism. This paradigm provides devices that can be seen as a network of hosts where the communication between them is controlled by a set of instructions that lead to the transmission of viruses. Virus machines can be seen as generating devices, computing devices and recognizing devices, depending on the possible input and the output of the systems. In this work, we present some machines generating basic sets, computing basic functions and we present recognizer virus machines, capable of solving decision problems in order to create a new complexity theory paradigm with virus machines.

Spiking neural P (SNP) systems are a class of neural-like computing models, abstracted by the mechanism of spiking neurons. This article proposes a new variant of SNP systems, called gated spiking neural P (GSNP) systems, which are composed of gated neurons. Two gated mechanisms are introduced in the nonlinear spiking mechanism of GSNP systems, consisting of a reset gate and a consumption gate. The two gates are used to control the updating of states in neurons. Based on gated neurons, a prediction model for time series is developed, known as the GSNP model. Several benchmark univariate and multivariate time series are used to evaluate the proposed GSNP model and to compare several state-of-the-art prediction models. The comparison results demonstrate the availability and effectiveness of GSNP for time series forecasting.

Coupled neural P (CNP) systems are a recently developed Turing-universal, distributed and parallel computing model, combining the spiking and coupled mechanisms of neurons. This paper focuses on how to apply CNP systems to handle the fusion of multi-modality medical images and proposes a novel image fusion method. Based on two CNP systems with local topology, an image fusion framework in nonsubsampled shearlet transform (NSST) domain is designed, where the two CNP systems are used to control the fusion of low-frequency NSST coefficients. The proposed fusion method is evaluated on 20 pairs of multi-modality medical images and compared with seven previous fusion methods and two deep-learning-based fusion methods. Quantitative and qualitative experimental results demonstrate the advantage of the proposed fusion method in terms of visual quality and fusion performance.

This paper discusses a new variant of spiking neural P systems (in short, SNP systems), spiking neural P systems with extended channel rules (in short, SNP-ECR systems). SNP-ECR systems are a class of distributed parallel computing models. In SNP-ECR systems, a new type of spiking rule is introduced, called ECR. With an ECR, a neuron can send the different numbers of spikes to its subsequent neurons. Therefore, SNP-ECR systems can provide a stronger firing control mechanism compared with SNP systems and the variant with multiple channels. We discuss the Turing universality of SNP-ECR systems. It is proven that SNP-ECR systems as number generating/accepting devices are Turing universal. Moreover, we provide a small universal SNP-ECR system as function computing devices.

Dendrite P systems (DeP systems) are a recently introduced neural-like model of computation. They provide an alternative to the more classical spiking neural (SN) P systems. In this paper, we present the first software simulator for DeP systems, and we investigate the key features of the representation of the syntax and semantics of such systems. First, the conceptual design of a simulation algorithm is discussed. This is helpful in order to shade a light on the differences with simulators for SN P systems, and also to identify potential parallelizable parts. Second, a novel simulator implemented within the P-Lingua simulation framework is presented. Moreover, MeCoSim, a GUI tool for abstract representation of problems based on P system models has been extended to support this model. An experimental validation of this simulator is also covered.

Based on the feature and communication of neurons in animal neural systems, spiking neural P systems (SN P systems) were proposed as a kind of powerful computing model. Considering the length of axons and the information transmission speed on synapses, SN P systems with delay on synapses (SNP-DS systems) are proposed in this work. Unlike the traditional SN P systems, where all the postsynaptic neurons receive spikes at the same instant from their presynaptic neuron, the postsynaptic neurons in SNP-DS systems would receive spikes at different instants, depending on the delay time on the synapses connecting them. It is proved that the SNP-DS systems are universal as number generators. Two small universal SNP-DS systems, with standard or extended rules, are constructed to compute functions, using 56 and 36 neurons, respectively. Moreover, a simulator has been provided, in order to check the correctness of these two SNP-DS systems, thus providing an experimental validation of the universality of the systems designed.

Several variants of spiking neural P systems (SNPS) have been presented in the literature to perform arithmetic operations. However, each of these variants was designed only for one specific arithmetic operation. In this paper, a complete arithmetic calculator implemented by SNPS is proposed. An application of the proposed calculator to information fusion is also proposed. The information fusion is implemented by integrating the following three elements: (1) an addition and subtraction SNPS already reported in the literature; (2) a modified multiplication and division SNPS; (3) a novel storage SNPS, i.e. a method based on SNPS is introduced to calculate basic probability assignment of an event. This is the first attempt to apply arithmetic operation SNPS to fuse multiple information. The effectiveness of the presented general arithmetic SNPS calculator is verified by means of several examples.

Tissue P systems with promoters provide nondeterministic parallel bioinspired devices that evolve by the interchange of objects between regions, determined by the existence of some special objects called promoters. However, in cellular biology, the movement of molecules across a membrane is transported from high to low concentration. Inspired by this biological fact, in this article, an interesting type of tissue P systems, called monodirectional tissue P systems with promoters, where communication happens between two regions only in one direction, is considered. Results show that finite sets of numbers are produced by such P systems with one cell, using any length of symport rules or with any number of cells, using a maximal length 1 of symport rules, and working in the maximally parallel mode. Monodirectional tissue P systems are Turing universal with two cells, a maximal length 2, and at most one promoter for each symport rule, and working in the maximally parallel mode or with three cells, a maximal length 1, and at most one promoter for each symport rule, and working in the flat maximally parallel mode. We also prove that monodirectional tissue P systems with two cells, a maximal length 1, and at most one promoter for each symport rule (under certain restrictive conditions) working in the flat maximally parallel mode characterizes regular sets of natural numbers. Besides, the computational efficiency of monodirectional tissue P systems with promoters is analyzed when cell division rules are incorporated. Different uniform solutions to the Boolean satisfiability problem (SAT problem) are provided. These results show that with the restrictive condition of "monodirectionality," monodirectional tissue P systems with promoters are still computationally powerful. With the powerful computational power, developing membrane algorithms for monodirectional tissue P systems with promoters is potentially exploitable.

Biological membranes play an active role in the evolution of cells over time. In the framework of Membrane Computing, P systems with active membranes capture this idea, and the possibility to increase the number of membranes during a computation. Classically, it has been considered, by using divisi on rules, inspired in the mitosis process. Initially, the membranes in these models are supposed to have an electrical polarization (positive, negative or neutral) and the semantics is minimalist, in the sense that rules are applied in parallel, but in one transition step, each membrane can be the subject of at most one rule of types communication, dissolution or division. This paper focuses on polarizationless P systems with active membranes in which membrane creation rules are considered instead of membrane division rules as a mechanism to construct an exponential workspace, expressed both in terms of number of objects and membranes, in linear time. Moreover, the minimalist semantics is considered and some complexity results are provided in this framework, allowing to tackle the P versus NP problem from a new perspective. An original frontier of the efficiency in this context is unveiled in this paper: allowing membrane creation rules to be applicable in any membrane of the system, instead of restricting them to only elementary membranes, yields a significant boost on the computational power. More precisely, only problems in P can be efficiently solved in the restricted case, while in the non-restricted case an efficient and uniform solution to a PSPACE-complete problem is provided.

This paper proposes a new variant of spiking neural P systems (in short, SNP systems), nonlinear spiking neural P systems (in short, NSNP systems). In NSNP systems, the state of each neuron is denoted by a real number, and a real configuration vector is used to characterize the state of the whole system. A new type of spiking rules, nonlinear spiking rules, is introduced to handle the neuron's firing, where the consumed and generated amounts of spikes are often expressed by the nonlinear functions of the state of the neuron. NSNP systems are a class of distributed parallel and nondeterministic computing systems. The computational power of NSNP systems is discussed. Specifically, it is proved that NSNP systems as number-generating/accepting devices are Turing-universal. Moreover, we establish two small universal NSNP systems for function computing and number generator, containing 117 neurons and 164 neurons, respectively.

This Fundamenta Informaticae special issue on "Bio-Inspired Computing: Theories and Applications" collects a selection of ten revised and extended papers presented at the 12th edition of the International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2017).BIC-TA is a series of conferences that aims to bring together researchers working in the main areas of natural computing inspired from biology, for presenting their recent results, exchanging ideas, and cooperating in a friendly framework.Since 2006, the conference was held in Wuhan

Polarizationless P systems with active membranes are non-cooperative systems, that is, the left-hand side of their rules have a single object. Usually, these systems make use of division rules as a mechanism to produce an exponential workspace in linear time. Division rules are inspired by cell div ision, a process of nuclear division that occurs when a parent cell divides to produce two identical daughter cells. On the other hand, separation rules are inspired by the membrane fission process, a mechanism by which a biological membrane is split into two new ones in such a manner that the contents of the initial membrane is distributed between the new membranes. In this paper, separation rules are used instead of division rules. The computational efficiency of these models is studied and the role of the (minimal) cooperation in object evolution rules is explored from a computational complexity point of view.

Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is w ell known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P. P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP-complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted.

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

This paper focuses on automatic fuzzy clustering problem and proposes a novel automatic fuzzy clustering method that employs an extended membrane system with active membranes that has been designed as its computing framework. The extended membrane system has a dynamic membrane structure; since membranes can evolve, it is particularly suitable for processing the automatic fuzzy clustering problem. A modification of a differential evolution (DE) mechanism was developed as evolution rules for objects according to membrane structure and object communication mechanisms. Under the control of both the object's evolution-communication mechanism and the membrane evolution mechanism, the extended membrane system can effectively determine the most appropriate number of clusters as well as the corresponding optimal cluster centers. The proposed method was evaluated over 13 benchmark problems and was compared with four state-of-the-art automatic clustering methods, two recently developed clustering methods and six classification techniques. The comparison results demonstrate the superiority of the proposed method in terms of effectiveness and robustness.

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

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.

P systems have been proven to be useful as modeling tools in many fields, such as Systems Biology and Ecological Modeling. For such applications, the acceleration of P system simulation is often desired, given the computational needs derived from the

This volume contains a selection of papers presented at the 9th edition of the international conference Bio-Inspired Computing: Theories and Applications, BIC

A membrane system (P system) is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P ≠ NP.

Membrane systems (also called P systems) refer to the computing models abstracted from the structure and the functioning of the living cell as well as from the cooperation of cells in tissues, organs, and other populations of cells. Spiking neural P systems (SNPS) are a class of distributed and parallel computing models that incorporate the idea of spiking neurons into P systems. To attain the solution of optimization problems, P systems are used to properly organize evolutionary operators of heuristic approaches, which are named as membrane-inspired evolutionary algorithms (MIEAs). This paper proposes a novel way to design a P system for directly obtaining the approximate solutions of combinatorial optimization problems without the aid of evolutionary operators like in the case of MIEAs. To this aim, an extended spiking neural P system (ESNPS) has been proposed by introducing the probabilistic selection of evolution rules and multi-neurons output and a family of ESNPS, called optimization spiking neural P system (OSNPS), are further designed through introducing a guider to adaptively adjust rule probabilities to approximately solve combinatorial optimization problems. Extensive experiments on knapsack problems have been reported to experimentally prove the viability and effectiveness of the proposed neural system.

This paper continues an investigation into bridging two research areas concerned with natural computing: membrane computing and reaction systems. More specifically, the paper considers a transfer of two assumptions/axioms of reaction systems, non-permanency and the threshold assumption, into the framework of membrane computing. It is proved that: (1) spiking neural P systems with non-permanency of spikes assumption characterize the semilinear sets of numbers, and (2) symport/antiport P systems with threshold assumption (translated as ω multiplicity of objects) can solve SAT in polynomial time. Also, several open research problems are stated.

Spiking neural P systems (SN P systems) are a new class of computing models inspired by the neurophysiological behavior of biological spiking neurons. In order to make SN P systems capable of representing and processing fuzzy and uncertain knowledge, we propose a new class of spiking neural P systems in this paper called weighted fuzzy spiking neural P systems (WFSN P systems). New elements, including fuzzy truth value, certain factor, weighted fuzzy logic, output weight, threshold, new firing rule, and two types of neurons, are added to the original definition of SN P systems. This allows WFSN P systems to adequately characterize the features of weighted fuzzy production rules in a fuzzy rule-based system. Furthermore, a weighted fuzzy backward reasoning algorithm, based on WFSN P systems, is developed, which can accomplish dynamic fuzzy reasoning of a rule-based system more flexibly and intelligently. In addition, we compare the proposed WFSN P systems with other knowledge representation methods, such as fuzzy production rule, conceptual graph, and Petri nets, to demonstrate the features and advantages of the proposed techniques.

We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open.

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.

In 1936 A. Turing showed the existence of a universal machine able to simulate any Turing machine given its description. In 1956, C. Shannon formulated for the first time the problem of finding the smallest possible universal Turing machine according to some critera to measure its size such as the number of states and symbols. Within the framework of Membrane Computing different studies have addressed this problem: small universal symport/antiport P systems (by considering the number of membranes, the weight of the rules and the number of objects as a measure of the size of the system), small universal splicing P systems (by considering the number of rules as a measure of the size of the system), and small universal spiking neural P systems (by considering the number of neurons as a measure of the size of the system). In this paper the problem of determining the smallest possible efficient P system is explicitly formulated. Efficiency within the framework of Membrane Computing refers to the capability of solving computationally hard problems (i.e. problems such that classical electronic computer cannot solve instances of medium/large size in any reasonable amount of time) in polynomial time. A descriptive measure to define precisely the notion of small P system is presented in this paper.

P systems or Membrane Systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems in a relevant and understandable way. They are inherently parallel and non-deterministic computing devices. In this article, we discuss the motivation, design principles and key of the implementation of a simulator for the class of recognizer P systems with active membranes running on a (GPU). We compare our parallel simulator for GPUs to the simulator developed for a single central processing unit (CPU), showing that GPUs are better suited than CPUs to simulate P systems due to their highly parallel nature.

A variant of spiking neural P systems with positive or negative weights on synapses is introduced, where the rules of a neuron fire when the potential of that neuron equals a given value. The involved values-weights, firing thresholds, potential consumed by each rule-can be real (computable) numbers, rational numbers, integers, and natural numbers. The power of the obtained systems is investigated. For instance, it is proved that integers (very restricted: 1, -1 for weights, 1 and 2 for firing thresholds, and as parameters in the rules) suffice for computing all Turing computable sets of numbers in both the generative and the accepting modes. When only natural numbers are used, a characterization of the family of semilinear sets of numbers is obtained. It is shown that spiking neural P systems with weights can efficiently solve computationally hard problems in a nondeterministic way. Some open problems and suggestions for further research are formulated.

Cell-like recognizing membrane systems are computational devices in the framework of membrane computing inspired from the structure of living cells, where biological membranes are arranged hierarchically. In this paper tissue-like recognizing membrane systems are presented. The idea is to consider that membranes are placed in the nodes of a graph, mimicking the cell intercommunication in tissues. In this context, polynomial complexity classes associated with recognizing membrane systems can be defined. We recall the definition for cell-like systems, and we introduce the corresponding complexity classes for the tissue-like case. Moreover, in this paper two efficient solutions to the satisfiability problem are analyzed and compared from a complexity point of view. © 2009 Wiley Periodicals, Inc.

In this paper, we describe a new representation for deterministic rational-valued P systems that allows us to form a bridge between membrane computing and linear algebra. On the one hand, we prove that an efficient computation for these P systems can be described using linear algebra techniques. In particular, we show that the computation for getting a configuration in such P systems can be carried out by multiplying appropriate matrices. On the other hand, we also show that membrane computing techniques can be used to get the nth power of a given matrix.

Quorum sensing is a cell-density-dependent gene regulation system that allows an entire population of bacterial cells to communicate in order to regulate the expression of certain or specific genes in a coordinated way depending on the size of the population. We present a model of the quorum sensing system in Vibrio fischeri using a variant of membrane systems called P systems. In this framework each bacterium and the environment are represented by membranes, and the rules are applied according to an extension of Gillespie's algorithm called the multicompartmental Gillespie's algorithm. This algorithm runs on more than one compartment and takes into account the disturbance produced when chemical substances diffuse from one compartment or region to another one. Our approach allows us to examine the individual behavior of each bacterium as an agent as well as the emergent behavior of the colony as a whole and the processes of swarming and recruitment. Our simulations show that at low cell densities bacteria remain dark, while at high cell densities some bacteria start to produce light and a recruitment process takes place that makes the whole colony of bacteria do so. Our computational modeling of quorum sensing could provide insights leading to new applications where multiple agents need to robustly and efficiently coordinate their collective behavior based only on very limited information about the local environment.