P colonies Abstract P colonies are abstract computing devices modelling communities of very simple reactive agents living and acting in a joint shared environment. The concept was motivated by so-called colonies, grammar systems based on interplay of very simple agents, on one hand, and by membrane systems, massively parallel computational models inspired by cell biology, on the other hand. Some variants of P colonies also allow the environment to participate actively in the system’s evolution. In this paper we summarize the most important results on P colonies, present open problems concerning these constructs, and suggest new research directions in their study.

Generating context-free languages using spiking neural P systems with structural plasticity Abstract Spiking neural P system (SNP system) is a model of computation inspired by networks of spiking neurons. An SNP system is a network of neurons that can send an object, known as a spike, to each other. Spiking neural P system with structural plasticity (SNPSP system) is a variant of the classical SNP system. SNPSP system that incorporates the ideas of synaptogenesis (creating new synapses) and synaptic pruning (deletion of existing synapses), collectively known as structural plasticity, as features of the model. This gives SNPSP systems the ability to change their own structure/topology. In this work, we use SNPSP systems to generate context-free languages. We create a procedure for constructing an SNPSP system given a context-free grammar in Greibach normal form (GNF). The resulting SNPSP system essentially simulates the way in which a context-free grammar in GNF is used to generate languages. We use modules known as arithmetic-memory modules, also created using SNPSP systems, to perform arithmetic operations which are needed for the simulation.

Metabolic computing Abstract The paper reviews some aspects of MP grammars, a particular type of P systems (M stands for Metabolic) consisting of multiset rewriting rules, which were introduced in the context of Membrane Computing, for modeling biological dynamics. The main features of MP theory are recalled, such as the control mechanisms based on regulation functions, MP graphs, representation of oscillatory dynamics, regression algorithms, and MP modeling. Finally, the computational universality of MP grammars is proved by means of Minsky’s register machines.

P systems attacking hard problems beyond NP: a survey Abstract In the field of membrane computing, a great attention is traditionally paid to the results demonstrating a theoretical possibility to solve NP-complete problems in polynomial time by means of various models of P systems. A bit less common is the fact that almost all models of P systems with this capability are actually stronger: some of them are able to solve PSPACE-complete problems in polynomial time, while others have been recently shown to characterize the class \(\mathbf {P^{\#P}}\) (which is conjectured to be strictly included in PSPACE). A large part of these results has appeared quite recently. In this survey, we focus on strong models of membrane systems which have the potential to solve hard problems belonging to classes containing NP. These include P systems with active membranes, P systems with proteins on membranes and tissue P systems, as well as P systems with symport/antiport and membrane division and, finally, spiking neural P systems. We provide a survey of computational complexity results of these membrane models, pointing out some features providing them with their computational strength. We also mention a sequence of open problems related to these topics.

Matrix representation and simulation algorithm of spiking neural P systems with structural plasticity Abstract In this paper, we create a matrix representation for spiking neural P systems with structural plasticity (SNPSP, for short), taking inspiration from existing algorithms and representations for related variants. Using our matrix representation, we provide a simulation algorithm for SNPSP systems. We prove that the algorithm correctly simulates an SNPSP system: our representation and algorithm are able to capture the syntax and semantics of SNPSP systems, e.g. plasticity rules, dynamism in the synapse set. Analyses of the time and space complexity of our algorithm show that its implementation can benefit using parallel computers. Our representation and simulation algorithm can be useful when implementing SNPSP systems and related variants with a dynamic topology, in software or hardware.

An interactive timeline of simulators in membrane computing Abstract As with any fast-emerging research front in computer science, the proliferation of theoretical and practical results within Membrane computing since its appearance in 1998 was astonishing. As a consequence, it became necessary during the subsequent years to produce several surveys collecting the main achievements from a theoretical point of view, along with some specific surveys about simulation tools for this paradigm. As the discipline has reached a certain degree of maturity, more practical applications have arisen, and new collective works are summarising the new software products appeared. However, while these recapitulation efforts remain useful for details about new simulators, they cannot act as exhaustive updated listings, as they become obsolete as soon as new tools are developed. Thus, we considered that it was necessary to provide an interactive tool showing an updated timeline (https://www.gcn.us.es/SimulationMC) about the simulation of the computational devices of membrane computing (a.k.a P systems), aiming to stay updated whenever any new practical work comes out in the discipline. This paper recalls the main stages and milestones within the evolution of simulation tools for different types and variants of P systems, along with their main related applications. In addition, it describes the interactive web tool with the timeline mentioned, where all the references related here have been incorporated. Unlike other survey papers, it is the intent of this work to reinforce this initial collective effort with the web endpoint kept alive and updated.

From biopolymer duplication to membrane duplication and beyond Abstract The relationship between biopolymer duplication and membranes compartmentation is analyzed, by stressing their intertwinement and the different monomers that determine their forms of aggregation (linear and circular) with their functions. Both polymers and membranes are prebiotic forms of molecular assemblies, but in their integration the seed of life emerges. From membranes hosting a replicative metabolism cells stem as living unities, where an almost perfect synthesis is realized between metabolism and duplication. What is missing to perfection becomes the basis of evolution. The whole logic of the processes at the origin of life is reconstructed in general terms, in the line of Manca (Infobiotics: information in biotic systems. Springer, New York, 2013), Manca (J Proteom Bioinform 11(7), 135–137, 2018) and Manca and Santagata (Un meraviglioso accidente. La nascita della vita. Mondadori, Italy, 2018), with no biochemistry detail, but only on the basis of the needs for representing, conserving, developing, and transmitting biological information.

Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems Abstract Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules; and (b) cell-like P systems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem.

A P system model of swarming and aggregation in a Myxobacterial colony Abstract Bacterial communities provide an interesting subject for the study of emergence and complexity as the consequence of many local interactions. In particular, the soil-dwelling social bacterium Myxobacteria demonstrates two distinct types of motility, social motility via the sensing of bacterial slime deposits and adventurous motility. Both modes of motility are governed by local interactions. Using P systems, a membrane computing methodology based on compartmental rewrite rules for modelling computational processes; this work demonstrates how minimal set of rules can model swarming and aggregating behaviour in Myxobacteria bacterial populations. Our model uses a multi-environment P system similar a 2D cellular automaton to represent the substrate environment whilst stochastic rule selection dictates Myxobacterial motion according to behaviour observed in vitro. The rules account for both mechanisms of motility, the deposit and detection of slime, a change in direction due to C-signal induction and the mixing of population numbers. Simulations demonstrate an extensible computational framework for the modelling of bacterial behaviour, with the potential for extension into additional emergent behaviours.

Polarization: a new communication protocol in networks of bio-inspired processors Abstract This work is a survey of the most recent results regarding the computational power of the networks of bio-inspired processors whose communication is based on a new protocol called polarization. In the former models, the communication amongst processors is based on filters defined by some random-context conditions, namely the presence of some symbols and the absence of other symbols. In the new protocol discussed here, a polarization (negative, neutral, and positive) is associated with each node, while the polarization of data navigating through the network is computed in a dynamical way by means of a valuation function. Consequently, the protocol of communication amongst processors is naturally based on the compatibility between their polarization and the polarization of the data. We consider here three types of bio-inspired processors: evolutionary processors, splicing processors, and multiset processors. A quantitative generalization of polarization (evaluation sets) is also presented. We recall results regarding the computational power of these networks considered as accepting devices. Furthermore, a solution to an intractable problem, namely the 0 / 1 Knapsack problem, based on the networks of splicing processors with evaluation sets considered as problem solving devices, is also recalled. Finally, we discuss some open problems and possible directions for further research in this area.