The aim of this research is to produce an algorithm for the software that would let a researcher to observe the evolution of maximally parallel multiset-rewriting systems with permitting and forbidding contexts, browsing the configuration space by following transitions like following hyperlinks in the World-Wide Web. The relationships of...
-
February 25, 2016 (v1)PublicationUploaded on: March 27, 2023
-
February 11, 2016 (v1)Publication
It is commonly believed that a signi¯cant part of the computational power of membrane systems comes from their inherent non-determinism. Re- cently, R. Freund and Gh. P¸aun have considered deterministic P systems, and formulated the general question whether the computing (generative) capacity of non-deterministic P systems is strictly larger...
Uploaded on: March 27, 2023 -
February 11, 2016 (v1)Publication
The usual assumption in P systems behavior is that of maximal parallelism, however in living cells it is not the case because they have a limited number of enzymes. The aim of this paper is to try to merge these ideas by introducing a notion of activator - a formal model of enzyme as a usual symbol- object, more or less a middle notion between...
Uploaded on: March 27, 2023 -
February 25, 2016 (v1)Publication
In this paper we consider symport/antiport P systems with one membrane and rules having at most two objects. Although it has been proved that only finite number sets can be generated by both OP1(sym2) (one-membrane systems with symport rules of weight at most 2) and OP1(sym1; anti1) (one-membrane systems with symport/antiport rules of weight...
Uploaded on: March 27, 2023 -
February 25, 2016 (v1)Publication
We consider P systems with only one membrane using symport/antiport rules and prove that any recursively enumerable set of k-dimensional vectors of natural numbers can be generated (accepted) by using at most k + 4 symbols; hence, any recursively enumerable set of natural numbers can be generated (accepted) by using at most five symbols.
Uploaded on: March 27, 2023 -
February 3, 2016 (v1)Publication
Membrane systems (with symbol objects) are formal models of distributed parallel multiset processing. Symport rules move multiple objects to a neighboring region. It is known that P systems with symport rules of weight at most 3 and a single membrane are computationally complete with 7 superfluous symbols. It is also known that without any...
Uploaded on: December 5, 2022 -
January 20, 2016 (v1)Publication
We continue the line of research of deterministic parallel non-cooperative multiset rewriting with control. We here generalize control, i.e., rule applicability context conditions, from promoters and inhibitors checking presence or absence of certain object up to some bound, to regular and even stronger predicates, focusing at predicates...
Uploaded on: December 2, 2022 -
March 18, 2016 (v1)Publication
Membrane computing is a formal framework of distributed parallel comput- ing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for one class and a negative conjecture is...
Uploaded on: December 2, 2022 -
January 20, 2016 (v1)Publication
The aim of this paper is to study the computational power of P systems with one active membrane without polarizations. For P systems with active membranes, it is known that computational completeness can be obtained with either of the following combinations of features: 1)two polarizations, 2)membrane creation and dissolution, 3)four membranes...
Uploaded on: March 27, 2023 -
February 3, 2016 (v1)Publication
Membrane systems (with symbol objects) are distributed controlled multiset processing systems. Non-cooperative P systems with either promoters or inhibitors (of weight not restricted to one) are known to be computationally complete. In this paper we show that the power of the deterministic subclass of such systems is computationally complete in...
Uploaded on: March 27, 2023 -
February 25, 2016 (v1)Publication
Membrane computing is a (biologically motivated) theoretical framework of distributed parallel computing. If symbol-objects are considered, then membrane sys- tems (also called P systems) are distributed multiset processing systems. In evolution- communication (EC) P systems the computation is carried out with the use of non- cooperative...
Uploaded on: December 5, 2022 -
January 25, 2016 (v1)Publication
Membrane systems (with symbol objects) are distributed controlled multiset processing systems. Non-cooperative P systems with either promoters or inhibitors (of weight not restricted to one) are known to be computationally complete. Since recently, it is known that the power of the deterministic subclass of such systems is subregular....
Uploaded on: March 27, 2023 -
February 11, 2016 (v1)Publication
The aim of this paper is to study the power of parallel multiset- rewriting systems with permitting context (or P systems with non-cooperative rules with promoters). The main result obtained is that if we use promoters of weight two, then the system is universal. Moreover, the construction satis¯es a special property we de¯ne: it is...
Uploaded on: March 27, 2023 -
February 11, 2016 (v1)Publication
In this paper we de¯ne a general class of P systems covering some biological operations with membranes, including evolution, communication, modifying the membrane structure, and we describe and formally specify some of these operations: membrane merging, membrane separation, membrane re- lease. We also investigate a particular combination of...
Uploaded on: March 27, 2023 -
November 29, 2016 (v1)Publication
We consider P systems only allowing rules to be used in at most one copy in each derivation step, especially the variant of the maximally parallel derivation mode where each rule may only be used at most once. Moreover, we also consider the derivation mode where from those sets of rules only those are taken which have the maximal number of...
Uploaded on: March 27, 2023 -
December 15, 2017 (v1)Publication
We introduce a novel kind of P systems in which the application of rules in each step is controlled by a function on the applicable multisets of rules. Some examples are given to exhibit the power of this general concept. Moreover, for three well-known models of P systems we show how they can be simulated by P systems with a suitable fairness function.
Uploaded on: March 27, 2023 -
December 15, 2017 (v1)Publication
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 de ne three variants of right-hand side randomization and compare each of them with the power of...
Uploaded on: March 27, 2023 -
March 1, 2019 (v1)Publication
We introduce new possibilities to control the application of rules based on the preceding applications, which can be de ned in a general way for (hierarchical) P systems and the main known derivation modes. Computational completeness can be obtained even for one-membrane P systems with non-cooperative rules and using both activation and...
Uploaded on: December 5, 2022 -
January 20, 2016 (v1)Publication
Toxic objects have been introduced to avoid trap rules, especially in (purely) catalytic P systems. No toxic object is allowed to stay idle during a valid derivation in a P system with toxic objects. In this paper we consider special variants of toxic P systems where the set of toxic objects is prede ned { either by requiring all objects to be...
Uploaded on: December 2, 2022 -
January 21, 2021 (v1)Publication
Catalytic P systems are among the rst variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particularly the problem of using only one catalyst: is one catalyst enough to allow for generating all recursively enumerable sets of...
Uploaded on: March 26, 2023 -
November 29, 2016 (v1)Publication
We consider (extended) spiking neural P systems with states, where the applicability of rules in a neuron not only depends on the presence of su ciently many spikes (yet in contrast to the standard de nition, no regular checking sets are used), but also on the current state of the neuron. Moreover, a spiking rule not only sends spikes, but also...
Uploaded on: March 27, 2023 -
February 3, 2016 (v1)Publication
We investigate the computational power of energy-based P systems, a model of membrane systems where a fixed amount of energy is associated with each object and the rules transform single objects by adding or removing energy from them. We answer recently proposed open questions about the power of such systems without priorities associated to the...
Uploaded on: March 27, 2023 -
February 11, 2016 (v1)Publication
P systems with active membranes using only two electrical charges and only rules of types (a) and (c) assigned to at most two membranes are shown to be computationally complete { thus improving the previous result of this type from the point of view of the number of polarizations as well as with respect to the number of membranes. Allowing a...
Uploaded on: December 4, 2022 -
March 1, 2019 (v1)Publication
We introduce new possibilities to control the application of rules based on the preceding application of rules which can be de ned for a general model of sequential grammars and we show some similarities to other control mechanisms as graph-controlled grammars and matrix grammars with and without applicability checking as well as gram- mars...
Uploaded on: March 27, 2023 -
January 25, 2016 (v1)Publication
In this paper we consider P systems with linear membrane structures (only one membrane is elementary) with at most one object. We raise and attack the question about the computational power of such systems, depending on the number of membrane labels, kinds of rules used, and some other possible restrictions.
Uploaded on: March 27, 2023