Introduced in [Erik Winfree, 1998], the abstract tile assembly model (aTAM) is a model of DNA self-assembly. Most of the studies focus on cooperative aTAM where a form of synchronization between the tiles is possible. Simulating Turing machines is achievable in this context. Few results and constructions are known for the non-cooperative case (a variant of Wang tilings [Hao Wang, 1961] where assemblies do not need to cover the whole plane and some mismatches may occur). For example, assembly of a square of width n is done with 2n-1 tiles types whereas only Θ(log(n)/(log log(n))) are required for the cooperative case [Leonard M. Adleman et al., 2001]. Introduced by P.-É. Meunier in [Meunier, 2015], efficient paths are a non-trivial construction for non-cooperative aTAM designed with n different tile types and reaching a distance linearly greater than n. Improved in [Pierre-Étienne Meunier and Damien Regnault, 2019], efficient paths were shown to be able to reach a distance of nlog(n). Assembling them relies heavily on a form of "non-determinism". Indeed, the set of tiles may produce different finite terminal assemblies but they all contain the same efficient path. In this paper, we prove that this non-determinism is strictly necessary for assembling the efficient paths of [Pierre-Étienne Meunier and Damien Regnault, 2019]. More formally, we show that if the terminal assembly of a directed non-cooperative tile assembly system (a model where only one terminal assembly is produced) is finite then its width and length are linear in the number of tiles. This result also implies that the construction of a square of width n using 2n-1 tiles types is asymptotically optimal. Moreover, we hope that the techniques introduced here will lead to a better comprehension of the non-directed case.

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.

Intuition tells us that highly complex structure should be strongly correlated with highly complex behavior. In this work, we show that, while complex behavior does require complex structure, the converse is not necessarily true. Indeed, structural complexity can be also used to implement robust behavior, or even a variety of different relatively simple behaviors. To obtain these results, we explored the spaces of sign Boolean networks (SBNs) containing 2, 3, and 4 nodes, and we used complexity measures introduced in our previous work to study the relationship between structural and behavioral complexities of these networks.

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

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.

In this article, we consider leftist insertion-deletion systems (LIDS), in which all rules have contexts on the same (left) side, and may only insert or delete one symbol at a time. We start by introducing extended rules, in which the contexts may be specified as regular expressions, instead of fix ed words. We prove that in this case the computational completeness is achieved when additional control mechanisms are used (graph control with two states, matrix control with binary matrices and random-context control). We then show how rules with regular contexts can be simulated by conventional rules checking one-symbol (resp. two-symbol) left contexts for insertion and two-symbol (resp. one-symbol) left contexts for deletion. This simulation does not generally hold in the controlled case, however. Hence, we provide a construction simulating an arbitrary 2-tag system using extended rules and which can be rewritten in terms of conventional rules of types above, which implies that the latter systems are universal.

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.

In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not.

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