Narrow Results

Gemmating P systems were introduced as a theoretical model based on the biological idea of the gemmation of mobile membranes. In the general model of extended gemmating P systems, strings are modified either by evolution rules in the membranes or while sending them to another membrane. We here consider the restricted variant of extended gemmating P systems with pre-dynamic rules where strings are only modified at the ends while sending them from one membrane to another one. In a series of papers the number of membranes being sufficient for obtaining computational completeness has steadily been decreased. In this paper we now prove the optimal result, i.e., gemmating P systems only using pre-dynamic rules are already computationally complete with three membranes, even in the non-extended case and with the minimal weight of rules possible. Moreover, we also show that for gemmating tissue P systems two cells suffice, and if we allow the environment to be fully involved in the communication of strings, even one cell together with the environment can manage the task to generate any recursively enumerable language.

Dynamical probabilistic P systems are discrete, stochastic, and parallel devices, where the probability values associated with the rules change during the evolution of the system. These systems are proposed as a novel approach to the analysis and simulation of the behavior of complex systems. We introduce all necessary definitions of these systems and of their dynamical aspects, we describe the functioning of the parallel and stochastic algorithm used in computer simulation, and evaluate its time complexity. Finally, we show some applications of dynamical probabilistic P systems for the investigation of the dynamics of the Lotka-Volterra system and of metapopulation systems.

We continue here the study of the recently introduced spiking neural P systems, which mimic the way that neurons communicate with each other by means of short electrical impulses, identical in shape (voltage), but emitted at precise moments of time. The sequence of moments when a neuron emits a spike is called the spike train (of this neuron); by designating one neuron as the output neuron of a spiking neural P system II, one obtains a spike train of II. Given a specific way of assigning sets of numbers to spike trains of II, we obtain sets of numbers computed by II. In this way, spiking neural P systems become number computing devices. We consider a number of ways to assign (code) sets of numbers to (by) spike trains, and prove then computational completeness: the computed sets of numbers are exactly Turing computable sets. When the number of spikes present in the system is bounded, a characterization of semilinear sets of numbers is obtained. A number of research problems is also formulated.

Spiking neural P systems were introduced in the end of the year 2005, in the aim of incorporating in membrane computing the idea of working with unique objects ("spikes"), encoding the information in the time elapsed between consecutive spikes sent from a cell/neuron to another cell/neuron. More than one dozen of papers where written in the meantime, clarifying many of the basic properties of these devices, especially related to their computing power.

The present paper quickly surveys the basic ideas and the basic results, presenting a complete to-date bibliography, and also giving a completing result related to the normal forms possible for spiking neural P systems: we prove that the indegree of such systems (the maximal number of incoming synapses of neurons) can be bounded by 2 without losing the computational completeness.

A series of research topics and open problems are formulated.

We introduce the notion of stateless multihead two-way (respectively, one-way) NFAs and stateless multicounter systems and relate them to P systems and vector addition systems. In particular, we investigate the decidability of the emptiness and reachability problems for these stateless automata and show that the results are applicable to similar questions concerning certain variants of P systems, namely, token systems and sequential tissue-like P systems.

Ramsey numbers deal with conditions when a combinatorial object necessarily contains some smaller given objects. It is well known that it is very difficult to obtain the values of Ramsey numbers. In this work, a theoretical chemical/biological solution is presented in terms of membrane computing for the decision version of Ramsey number problem, that is, to decide whether an integer n is the value of Ramsey number R(k, l), where k and l are integers.

The paper summarizes recent knowledge about computational power of spiking neural P systems and presents a sequence of new more general results. The concepts of recognizer SN P systems and of uniform families of SN P systems provide a formal framework for this study. We establish the relation of computational power of spiking neural P systems with various limitations to standard complexity classes like P, NP, PSPACE and P/poly.

In living cells, the diffusion of molecules is fundamental for the proper functioning of many intracellular processes and for their correct response to external or internal signaling. In this paper, we consider the diffusion of a pivotal protein involved in bacterial chemotaxis, and show how to model and simulate the formation of concentration gradients of this protein along the bacterial cell. For this purpose, we exploit the framework of P systems to represent the partition of the bacterial volume into separate but communicating virtual volumes, and make use of communication rules to mimic the diffusive events. We simulate this system by means of the multivolume stochastic simulation algorithm τ-DPP, and present the effects of different diffusion coefficients and of a varying number of virtual volumes over the response of the chemotactic pathway.

This paper discusses research frontiers of membrane computing by presenting current open problems and research topics, together with the relevant background and motivation.

Spiking Neural $P$ 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 $P$ 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 $P$ 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.

In the present work, a novel communication strategy among neurons of Spiking Neural $P$ Systems is proposed. In the resulting models, called Spiking Neural $P$ 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 $P$ 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).

The Spiking Neural $P$ 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.

The optimization of robot controller parameters is a crucial task for enhancing robot performance, yet it often presents challenges due to the complexity of multi-objective, multi-dimensional multi-parameter optimization. This paper introduces a novel approach aimed at efficiently optimizing robot controller parameters to enhance its motion performance. While spiking neural P systems have shown great potential in addressing optimization problems, there has been limited research and validation concerning their application in continuous numerical, multi-objective, and multi-dimensional multi-parameter contexts. To address this research gap, our paper proposes the Entropy-Weighted Numerical Gradient Optimization Spiking Neural P System, which combines the strengths of entropy weighting and spiking neural P systems. First, the introduction of entropy weighting eliminates the subjectivity of weight selection, enhancing the objectivity and reproducibility of the optimization process. Second, our approach employs parallel gradient descent to achieve efficient multi-dimensional multi-parameter optimization searches. In conclusion, validation results on a biped robot simulation model show that our method markedly enhances walking performance compared to traditional approaches and other optimization algorithms. We achieved a velocity mean absolute error at least 35% lower than other methods, with a displacement error two orders of magnitude smaller. This research provides an effective new avenue for performance optimization in the field of robotics.

ALL-SAT problem is one of SAT problem’s special forms, which searches all assignment which can satisfies the given clause set. Membrane computing is a branch of natural computing which can solve NP problems in polynomial time with a parallel compute mode. This paper proposes a new algorithm for ALL-SAT problem which combines the traditional membrane computing algorithm of ALL-SAT problem with a concept called full-length clauses, which can reduce the space complexity and simplify the structure of the algorithm significantly.