Abstract During evolution, some living systems grow more complex. They develop new functions and new structures: flying and wings, digestion and digestive systems, swimming and fins, etc. Due to natural selection, this increase in complexity must be operated while keeping livelihood, i.e., the new structures and functions are added while maintaining the original behavior. In this work, we continue the effort of representing the phenomenon of structural and behavioral extension in abstract discrete dynamical systems in order to elucidate some big-picture tendencies. We choose reaction systems as the formal tool, and propose a translation into this new language of the extensibility framework we developed previously. We argue that using reaction systems makes definitions lighter and therefore should allow for better insights from future exhaustive exploration of the extension space.

Abstract The busy beaver game was introduced by Tibor Radó in 1962 and consists in finding the longest halting run that can be achieved by a Turing machine with a given number of states n . The function $$\text {BB}(n)$$ BB ( n ) measuring this length is a well-studied example of an uncomputable function. In this work, we transpose the concept of the busy beaver game to reaction systems—a set rewriting-based model of computing inspired by biochemical reactions. We give a generalized framework for defining various busy beaver challenges and give concrete instantiations for longest runs, periods, preperiods, etc. We further list several busy beaver champions and bounds, depending on what is optimized and what is measured as the size of a reaction system. Finally, we discuss possible implications of our work to thinking about theoretical biology.

A Boolean network is a discrete dynamical system operating on vectors of Boolean variables. The action of a Boolean network can be conveniently expressed as a system of Boolean update functions, computing the new values for each component of the Boolean vector as a function of the other components. Boolean networks are widely used in modeling biological systems that can be seen as consisting of entities which can be activated or deactivated, expressed or inhibited, on or off. P systems on the other hand are classically introduced as a model of hierarchical multiset rewriting. However, over the years the community has proposed a wide range of P system variants including diverse ingredients suited for various needs. In this work, we propose a new variant—Boolean P systems—specifically designed for reasoning about sequential controllability of Boolean networks, and use it to first establish a crisp formalization of the problem, and then to prove that the problem of sequential controllability is PSPACE -complete. We further claim that Boolean P systems are a demonstration of how P systems can be used to construct ad hoc formalisms, custom-tailored for reasoning about specific problems, and providing new advantageous points of view.

International audience

In this paper we consider prescribed sets of rules working on several objects either in parallel – in this case the rules have to take different objects – or else sequentially in any order – in this case several rules may take the same object to work on. We show that prescribed teams of size two, i.e., containing exactly two rules, are sufficient to obtain computational completeness for strings with the simple rules being of the form $$aI_R(b)$$ – meaning that a symbol b can be inserted on the right-hand side of a string ending with a – and $$D_R(b)$$ meaning that a symbol b is erased on the right-hand side of a string. This result is established for systems starting with three initial strings. Using prescribed teams of size three, we may start with only two strings, ending up with the output string and the second string having been reduced to the empty string. We also establish similar results when using the generation of the anti-object $$b^-$$ on the right-hand side of a string instead of deleting the object b, i.e. $$bI_R(b^-)$$ inserts the anti-object $$b^-$$ and the annihilation rule $$b\,b^-$$ assumed to happen immediately whenever b and $$b^-$$ meet deletes the b.

Catalytic P systems and purely catalytic P systems are among the first variants of membrane systems ever considered in this area. These variants of systems also feature some prominent computational complexity questions, and in particular the problem if only one catalyst in catalytic P systems and two catalysts in purely catalytic P systems are enough to allow for generating all recursively enumerable sets of multisets. Several additional ingredients have been shown to be sufficient for obtaining such results. Previously, we could show that using the derivation mode maxobjects, where we only take those multisets of rules which affect the maximal number of objects in the underlying configuration, one catalyst is sufficient for obtaining computational completeness without any other ingredients in catalytic P systems. In this paper we investigate the question whether we can obtain a similar result for purely catalytic P systems, i.e., we show that two catalysts in purely catalytic P systems are enough to allow for generating all recursively enumerable sets of multisets when using specific variants of the maximally parallel derivation mode: we take only those applicable multisets of rules which (i) generate the maximal number of objects, or (ii) yield the maximal difference in the number of objects between the newly generated configuration and the current configuration. In addition, we also consider non-extendable multisets of rules which (i) generate the minimal number of objects, or (ii) yield the minimal difference in the number of objects between the newly generated configuration and the current configuration. In all cases, we have also shown that register machines with n decrementable registers can be simulated by simple purely catalytic P systems working in any of these derivation modes using only n catalysts. Hence, simple purely catalytic P systems working in any of these derivation modes are computationally complete.

We extend and refine previous results within the general framework for regulated rewriting based on the applicability of rules in sequential grammars [3]. Besides the well-known control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, and priority relations on rules we also consider the new variant of activation and blocking of rules as investigated in [1, 2, 4]. Moreover, we exhibit special results for strings and multisets as well as for arrays in the general variant defined on Cayley grids of finitely presented groups. Especially we prove that array grammars defined on Cayley grids of finitely presented groups using #-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules, priority relations on rules, or activation and blocking of rules have the same computational power as such array grammars using arbitrary array productions.

P systems are a model of distributed and compartmentalized multiset rewriting, complete with various signal transmission mechanisms. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We define three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides. Finally, we also discuss extensions of the three variants to tissue P systems, i.e., P systems on an arbitrary graph structure.

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, different 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 efficiently 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.

We introduce new possibilities to control the application of rules based on the preceding applications, which can be defined in a general way for (hierarchical) P systems and the main known derivation modes. Computational completeness can be obtained even with non-cooperative rules and using both activation and blocking of rules, especially for the set modes of derivation, when allowing derivation steps with no rules being applied. When we allow the application of rules to influence the application of rules in previous derivation steps, applying a non-conservative semantics for what we consider to be a valid infinite derivation, we can even “go beyond Turing”.

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.

We introduce new possibilities to control the application of rules based on the preceding application of rules which can be defined for a general model of sequential grammars and we show some similarities with other control mechanisms such as graph-controlled grammars and matrix grammars with and without appearance checking, as well as grammars with random context conditions. Using both activation and blocking of rules, in the string and in the multiset case we can show computational completeness of context-free grammars equipped with the control mechanism of activation and blocking of rules even when using only two nonterminal symbols. With one- and two-dimensional $$\#$$ -context-free array grammars, computational completeness can already be obtained by only using activation of rules.

We consider extended spiking neural P systems with the additional possibility of so-called "white hole rules", which send the complete contents of a neuron to other neurons, and we prove that this extension of the original model can easily simulate register machines. Based on this proof, we then define red-green variants of these extended spiking neural P systems with white hole rules and show how to go beyond Turing with these red-green systems. We also discuss the number of actor neurons needed, and the relation of this model to some special variants of Lindenmayer systems.

The objective of this work is to present concrete membrane systems generating non-semilinear sets that are small in the following sense: Attention is paid to such parameters of descriptional complexity as the alphabet size, the number of rules, the total number of inhibitors used, and the maximal rule size. A total of 54 systems is described, depending on the exact goal; the presented systems for the same goal are incomparable.

We consider d -dimensional contextual array grammars and investigate their computational power when using various control mechanisms – matrices, regular control languages, and tissue P systems, which work like regular control languages, but may end up with a final check for the non-applicability of some rules. For d ≥ 2 , d -dimensional contextual array grammars are less powerful than matrix contextual array grammars, which themselves are less powerful than contextual array grammars with regular control languages. The use of tissue P systems with their final non-applicability check even yields some additional computational power. In the 1-dimensional case, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages can be characterized as the family of array images of the linear languages, which for a one-letter alphabet means that it coincides with the family of regular 1-dimensional array languages.

A hybrid network of evolutionary processors (HNEP) is a graph where each node is associated with a special rewriting system called an evolutionary processor, an input filter, and an output filter. Each evolutionary processor is given a finite set of one type of point mutations (insertion, deletion or a substitution of a symbol) which can be applied to certain positions in a string. An HNEP rewrites the strings in the nodes and then re-distributes them according to a filter-based communication protocol; the filters are defined by certain variants of random-context conditions. HNEPs can be considered both as languages generating devices (GHNEPs) and language accepting devices (AHNEPs); most previous approaches treated the accepting and generating cases separately. For both cases, in this paper we show that five nodes are sufficient to accept (AHNEPs) or generate (GHNEPs) any recursively enumerable language by showing the more general result that any partial recursive relation can be computed by an HNEP with (at most) five nodes with the underlying graph structure for the communication between the evolutionary processors being the complete or the linear graph with five nodes, whereas with a star-like communication graph we need six nodes. If the final results are defined by only taking the terminal strings out of the designated output node, then for these extended HNEPs we can prove that only four nodes are needed in all cases—for computing any partial recursive relation as well as for generating and accepting any recursively enumerable language—and the underlying communication structure can be a complete or a linear graph, but now even a star-like graph, too.

Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky's reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transform the universal machines U 22 and U 20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result.

In this paper, we examine P systems with a linear membrane structure, i.e., P systems in which only one membrane is elementary and the output of which is read out as the sequence of membrane labels in the halting configuration or vectors/numbers repr

It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [9], T

It is known that insertion-deletion (P) systems with two symbols context-free insertion and deletion rules are not computationally complete. It is thus interesting to consider conditions that would allow such systems to reach computational completeness. In this paper we consider insertion-deletion P systems with insertion and deletion operations applied only at the ends of string (we call them exo-operations). We show that such systems with one-symbol insertion and deletion of up to two symbols are computationally complete, and so are systems with insertion of up to two symbols and one-symbol deletion. The question about the computational power of insertion-deletion P systems with one-symbol insertion and one-symbol deletion operations applied at the ends of string is open. However, the tissue P systems reach computationally completeness even in this case.

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.

We consider the networks of evolutionary processors (NEP) introduced by J. Castellanos, C. Martí n-Vide, V. Mitrana and J. Sempere recently. We show that every recursively enumerable (RE) language can be generated by an NEP with three nodes modulo a terminal alphabet and moreover, NEPs with four nodes can generate any RE language. Thus, we improve existing universality result from five nodes down to four nodes. For mNEPs (a variant of NEPs where operations of different kinds are allowed in the same node) we obtain optimal results: each RE language can be generated by an mNEP with one node modulo a terminal alphabet, and mNEPs with two nodes can generate any RE language; this is not possible for mNEPs with one node. Some open problems are formulated.

The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP -complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space – membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.

This paper addresses the problem of removing the polarization of membranes from P systems with active membranes - and this is achieved by allowing the change of membrane labels by means of communication rules or by membrane dividing rules. As consequences of these results, we obtain the universality of P systems with active membranes which are allowed to change the labels of membranes, but do not use polarizations. Universality results are easily obtained also by direct proofs. By direct constructions, we also prove that SAT can be solved in linear time by systems without polarizations and with label changing possibilities. If non-elementary membranes can be divided, then SAT can be solved in linear time without using polarizations and label changing. Several open problems are also formulated.