Search

We consider tissue P systems working in the sequential mode on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. In a computation step, one rule is to be applied if possible, and then, in any case, the whole multiset being enclosed in a vesicle moves to one of the cells as indicated by the underlying graph structure of the system. The target cell is chosen in a non-deterministic way and does not depend on the possibly applied rule. With defining halting as reaching the final cell with a vesicle only containing terminal symbols, computational completeness can be obtained. Imposing the restriction that in each derivation step one rule has to be applied, we only reach the computational power of matrix grammars for multisets. Moreover, we also discuss variants for computations on strings. Finally, we outline a way how to “go beyond Turing” like with red-green register machines.

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 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 derivation step, we can even “go beyond Turing”.

In this paper, the computational power of several control mechanisms for specific variants of (sequential, isometric) array grammars generating arrays on Cayley grids of finitely presented groups is investigated. Using \(\#\)-context-free array productions together with control mechanisms as control graphs, matrices, permitting and forbidden rules, partial order on rules or activation and blocking of rules the same computational power is obtained as when using arbitrary array productions.

P systems are a model of hierarchically compartmentalized multiset rewriting. 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.

We show multiple ways of how to simulate R systems by non-cooperative P systems with atomic control by promoters and/or inhibitors, or with matter/antimatter annihilation rules, with a slowdown by a constant factor only. The descriptional complexity of the simulating P systems is also linear with respect to that of the simulated R system. All constants depend on how general the model of R systems is, as well as on the chosen control ingredients of the P systems. Special attention is paid to the differences in the mode of rule application in these models.

International audience; We investigate the computational power of d-dimensional contextual array grammars with matrix control and regular control languages. For $$d\ge 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. Yet in the 1-dimensional case, for a one-letter alphabet, the family of 1-dimensional array languages generated by contextual array grammars with regular control languages coincides with the family of regular 1-dimensional array languages, whereas for alphabets with more than one letter, we obtain the array images of the linear languages.

We consider the external variant of non-isometric d-dimensional contextual array grammars with regular control together with local selectors allowing for controlling how d-dimensional arrays are evolving by adjoining rectangular \((d-1)\)-dimensional arrays. In the 1-dimensional case, the computational power of these non-isometric contextual array grammars with regular control and local selectors equals the computational power of isometric contextual array grammars with regular control. The string images of the langauges of 1-dimensional arrays generated by these contextual array grammars exactly yield the linear languages. In the more-dimensional case, non-isometric d-dimensional contextual array grammars with regular control and local selectors can simulate the computations of \((d-1)\)-dimensional array grammars or Turing machines. Hence, for example, the emptiness problem for non-isometric d-dimensional contextual array grammars with regular control and local selectors for \(d>1\) is undecidable.

In this paper we extend the definition of a multiset by allowing elements to have multiplicities from an arbitrary totally ordered Abelian group instead of only using natural numbers. We consider P systems with such generalized multisets and give well-founded notations for the applicability of rules and for different derivation modes. These new definitions raise challenging mathematical questions and we propose several solutions yielding models sometimes having quite unexpected behavior. Another interesting application of our results is the possibility to consider complex objects and to manipulate them directly in a P system instead of their numerical encodings.

Motivated by the conceptual similarity of a mind change of a red-green Turing machine and of a turn to the complementary word in Watson-Crick L systems as well as by the fact that both red-green Turing machines and Watson-Crick L systems define infinite runs, we establish a connection between the two areas of unconventional computing. We show that the sets of numbers which can be recognized by so-called standard Watson-Crick T0L systems coincide with those recognized by red-green register machines (or red-green Turing machines). The results imply that using Watson-Crick L systems we may “go beyond Turing” in a similar way as red-green register machines and red-green Turing machines can do.

In this paper we investigate several variants of P automata having infinite runs on finite inputs. By imposing specific conditions on the infinite evolution of the systems, it is easy to find ways for going beyond Turing if we are watching the behavior of the systems on infinite runs. As specific variants we introduce a new halting variant for P automata which we call partial adult halting with the meaning that a specific predefined part of the P automaton does not change any more from some moment on during the infinite run. In a more general way, we can assign \(\omega \)-languages as observer languages to the infinite runs of a P automaton. Specific variants of regular \(\omega \)-languages then, for example, characterize the red-green P automata.

We show that catalytic P systems with one catalyst can simulate partially blind register machines and partially blind counter automata. To demonstrate their capability, we also present an example of a P automaton with one catalyst accepting a language with non-semilinear Parikh image as well as an example of a P system with one catalyst generating a non-semilinear vector set.

We present a number of tiny P systems generating or accepting nonsemilinear sets of (vectors of) natural numbers with very small numbers of rules, even for 1, 2, 3, 4, and 5 rules, depending on the particular model and the additional features used in these systems. Among the models we consider are P systems with target agreement and target selection, P systems with promoters and inhibitors, catalytic and purely catalytic P systems with normal catalysts or bi-stable catalysts. We then improve the results for catalytic (purely catalytic) P systems: 14 rules for generating a non-semilinear vector set and 29 rules for generating a non-semilinear number set are sufficient when allowing only the minimal number of two (three) catalysts; only 23 rules are needed if we allow more catalysts, i.e., five (seven) catalysts. Moreover,we introduce the new concept of toxic objects, objects that must not stay idle as otherwise the computation is abandoned without yielding a result. P systems of various kinds using toxic objects allow for smaller descriptional complexity, especially for smaller numbers of rules, as trap rules can be avoided.

Acceptance and recognizability of finite strings by red–green Turing machines are defined via infinite runs on the input string and the way how to distinguish between red and green states. We extend the notion of red–green Turing machines to register machines with an input tape and then to several variants of P automata. In order to allow for correct simulations of infinite computations of register machines, the models of P automata have to avoid trapping leading to unwanted infinite computations. Therefore, besides the original model of P automata using antiport rules we here consider two models introduced just recently and also allowing for deterministic simulations of register machine instructions, i.e., we consider the models of P systems with anti-matter as well as catalytic P systems with toxic objects. For all these models of P automata we define their red–green variants and show that they can simulate red–green register machines and therefore red–green Turing machines.

We introduce the new concept of toxic objects, objects that must not stay idle as otherwise the computation is abandoned without yielding a result. P systems of many kinds using toxic objects allow for smaller descriptional complexity, especially for smaller numbers of rules, as trap rules can be avoided. Besides presenting a number of tiny P systems generating or accepting non-semilinear sets of (vectors of) natural numbers with very small numbers of rules, we also improve the results for catalytic and purely catalytic P systems: \(14\) rules for generating a non-semilinear vector set and \(29\) rules for generating a non-semilinear number set are sufficient when allowing only the minimal number of two and three catalysts, respectively; moreover, with using toxic objects, these numbers can be reduced to \(11\) and \(17\). Yet only \(23\) rules – without using toxic objects – are needed if we allow for using more catalysts, i.e., five for catalytic P systems and seven catalysts for purely catalytic P systems.

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 improve previous results by showing 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.

The concept of a matter object being annihilated when meeting its corresponding anti-matter object is investigated in the context of P systems. Computational completeness can be obtained with using only non-cooperative rules besides these matter/anti-matter annihilation rules if these annihilation rules have priority over the other rules. Without this priority condition, in addition catalytic rules with one single catalyst are needed to get computational completeness. Even deterministic systems are obtained in the accepting case. Allowing anti-matter objects as input and/or output, we even get a computationally complete computing model for computations on integer numbers. Interpreting sequences of symbols taken in from and/or sent out to the environment as strings, we get a model for computations on strings, which can even be interpreted as representations of elements of a group based on a computable finite presentation.