Sequential and maximally parallel multiset rewriting: reversibility and determinism

Abstract

We study reversibility and determinism aspects and the strong versions of these properties of sequential multiset processing systems and of maximally parallel systems, from the computability point of view. In the sequential case, syntactic criteria are established for both strong determinism and strong reversibility. In the parallel case, a criterion is established for strong determinism, whereas strong reversibility is shown to be decidable. In the sequential case, without control all four classes—deterministic, strongly deterministic, reversible, strongly reversible—are not universal, whereas in the parallel case deterministic systems are universal. When allowing inhibitors, the first and the third class become universal in both models, whereas with priorities all of them are universal. In the maximally parallel case, strongly deterministic systems with both promoters and inhibitors are universal. We also present a few more specific results and conjectures.

1 Introduction

The object of study in this paper is the computational model called multiset processing. In the sequential case, it can be interpreted as scattered context grammars, in the sense that the positions of symbols are irrelevant. The further ingredients we can use are promoters (also known as permitting context), inhibitors (also known as forbidden context) and priorities; we say that systems are without control if none of these ingredients is used. The reader can find the definition of these grammars and these controls, e.g., in (Dassow and Păun 1989). Multiset processing is also closely related to membrane systems, see (Păun 2002), working within only one membrane, either in a sequential way or with maximal parallelism (which is the basic transition mode used in the area of membrane systems).

If a fixed enumeration of the elements of the alphabet is assumed, then multisets are isomorphic to vectors. In that sense, sequential multiset processing corresponds to vector addition systems (see, e.g., Freund et al. 2005). Alternatively, adding and removing symbols can be viewed as incrementing and decrementing counters, i.e., vector addition systems may be viewed as a variant of stateless counter machines (as multitape non-writing Turing machines), where for every instruction it is specified for each counter which integer is to be added to it, yet not restricted to −1, 0 or 1; such a variant is also equivalent to multiset processing systems (in this case, testing for zero corresponds to using inhibitors).

The aim of this paper is to consider such properties of multiset rewriting systems as reversibility and determinism as well as their strong versions.

Reversibility is an important property of computational systems. It has been well studied for circuits of logical elements (Fredkin and Toffoli 1982), circuits of memory elements (Morita 2001), cellular automata (Morita 2007), Turing machines (Bennett 1973; Morita and Yamaguchi 2007), register machines (Morita 1996). Reversibility as a syntactical property is closely related to the microscopic physical reversibility, and thus it assumes better miniaturization possibilities for potential implementation. Moreover, reversibility essentially is backward determinism.

Sequential reversible P systems have been considered in (Leporati et al. 2006), in the energy-based model, simulating Fredkin gates and thus reversible circuits. The maximally parallel case of reversible multiset rewriting systems has been considered in (Alhazov and Morita 2010); such systems are universal with priorities or inhibitors, and it follows that reversibility is undecidable in these cases. In (Alhazov and Morita 2010) also strong reversibility is considered as extending the requirement for reversibility in such a way that it does not depend on the initial configuration, and a characterization of strongly reversible systems without control is given. It has been shown in (Ibarra 2011) that even for parallel multiset rewriting systems strong reversibility is decidable. Moreover, in (Alhazov and Morita 2010) strong determinism is defined, and a syntactic criterion for it is given showing that the power of strongly deterministic systems is weaker than that of deterministic systems. It was natural to ask similar questions for sequential multiset rewriting systems as then done in (Alhazov et al. 2010).

This paper is an extended version of (Alhazov et al. 2010); we here compare the results obtained for sequential systems obtained in (Alhazov et al. 2010) with the results obtained for maximally parallel systems in (Alhazov and Morita 2010). While revisiting the results from (Alhazov and Morita 2010) we also answer a few questions left open there. The structure of the presentation is as follows: we first give the relevant definitions and then illustrate reversibility and strong reversibility for the case of sequential multiset rewriting systems by some examples. We continue with elaborating the results for the computational power of these sequential multiset rewriting systems as well as with the results for determinism and strong determinism. We proceed with investigating the same questions for the maximally parallel case. We conclude with a summary of the results shown in this paper.

2 Definitions and main concepts

2.1 Reversibility and determinism

Any discrete transition system is characterized by defining transitions between its instantaneous descriptions, typically referred to as configurations. The number of configurations is typically countably infinite, while the mechanism of defining the transitions normally has some finite description. If the system may perform a transition from configuration C into configuration $C^{\prime}$, we say that C is a preimage of $C^{\prime}$. Reachability relation is the transitive closure of the transition relation. In many systems, one configuration or a specific subset of configurations is distinguished and referred to as the initial one(s). Moreover, certain configurations are distinguished and called final. A system is viewed as a generating device when one examines the final configurations reachable from the starting one. It is viewed as an accepting device when one is concerned about reachability of the final configurations from different starting ones. Each sequence of transitions defining reachability in these cases is called a computation.

Throughout this paper, by reachable we mean reachable from the initial configuration. We now define two properties; extending the requirement from reachable configurations to all configurations, we obtain their strong variants.

Definition 1

We call a transition system $\Uppi$ strongly reversible if every configuration has in-degree at most one; $\Uppi$ is called reversible if every reachable configuration has in-degree at most one. We call $\Uppi$ strongly deterministic if every configuration has out-degree at most one; $\Uppi$ is called deterministic if every reachable configuration has out-degree at most one.

The strong reversibility refers to in-degrees of all configurations, and the strong determinism refers to out-degrees of all configurations. On the other hand, the properties reversibility and determinism only refer to the configurations in the actual computation of the system.

Note that it is crucial even for the (not-strong) reversibility that the in-degree is understood as the number of transitions into the given configuration from all preimages, not only from the reachable ones, otherwise the concept of reversibility may become trivial (in practice, at least any deterministic system can be modified to satisfy such a property, e.g., by additionally implementing some step counter).

Note that the concept of reversibility defined above (one may call it logical reversibility) is not related with the possibility of the system itself to return to previous configurations (one may call it recurrence), or with the possibility of the individual underlying rules to be undone by the system itself (one may call it chemical reversibility); these may or may not hold, and constitute different concepts that we do not address in the rest of the paper.

2.2 Multiset rewriting

Consider a finite alphabet O. A multiset over O is a mapping ${M:O\rightarrow \mathbb{N}}$. In this paper we represent a multiset M by any string $w\in O^{*}$ such that |w| _a  = M(a) for $a\in O$, keeping in mind that the order of symbols is not important. We use notations of set inclusions and set difference for multisets, meaning ≤ and max(difference, 0) for every symbol a, respectively.

A multiset rewriting rule is given by $r:u\rightarrow v$, where $u\in O^+,\,v\in O^{*}$. This rule can be applied to a multiset w if |w| _a  ≥ |u| _a for all $a\in O$, and the result is $w^{\prime}$, denoted $w\Rightarrow w^{\prime}$, if $|wv|_a=|w^{\prime}u|_a$ for all $a\in O$. If a rule has a promoter a, we write it as $u\rightarrow v|_a$. If a rule has an inhibitor a, we write it as $u\rightarrow v|_{\neg a}$. The priority relationship is denoted by >. We also refer to u and v as lhs(r) and rhs(r) if $r:u\rightarrow v$ (even if it has a promoter or an inhibitor). Applicability of rules with additional control depends on the corresponding condition (presence of symbol a, absence of symbol a, or inapplicability of rules with higher priority, respectively). In the following we will not speak about promoters in the sequential case, as rules $u\rightarrow v|_{a}$ and $ua\rightarrow va$ then are equivalent. In the sequential case, the relation ⇒ is defined as the union of relations corresponding to the application of all rules.

A multiset rewriting system is a tuple (O, T, w ₀, R), where O is the alphabet, T is the terminal alphabet, w ₀ is the initial multiset, and R is a (non-empty) finite set of rules. In the accepting case, T is the input alphabet, and the computation starts when an arbitrary multiset over T is added to w ₀. Consider a multiset rewriting system $\Uppi$ with alphabet O. A configuration is a multiset u. The space $\mathcal{C}$ of configurations (i.e., of multisets over O) is essentially an |O|-dimensional space with non-negative integer coordinates. The relation ⇒ induces an infinite labeled graph on $\mathcal{C}$ (with each configuration labeling a node and each set of rules whose application leads from a configuration C to a configuration $C^{\prime}$ labeling an edge leading from C to $C^{\prime}$). The halting configurations (and only these) have out-degree zero.

2.3 Maximal parallelism

The second part of the results in this paper considers a model where instead of applying one rule at each step, a multiset of rules is applied. Moreover, it is required that the chosen multiset of rules is not extendable; this is the usual definition of maximally parallel transitions (Păun 2002). We refer to this variant as P systems for short, see Note 1. Most of the corresponding results have first been shown in (Alhazov and Morita 2010), where the presentation has been done in terms of one-membrane symport/antiport P systems, with the environment containing an unbounded supply of all objects, see Note 2.

Note 1

In fact, there exists a large variety of models and variants of P systems, including the ones with sequential mutliset rewriting. Yet, maximal parallelism remains by far the most studied transition mode, so in this paper we say P system to assume maximal parallelism.

Note 2

It is well-known that rules in symport/antiport systems can be represented as cooperative rewriting rules on objects of the form (object, region). It is also known that, in case the environment contains an unbounded supply of all objects, any symport/antiport rule u/v (meaning u goes out and v comes in) is equivalent to a multiset rewriting rule $u\rightarrow v$ (clearly, symport-in rules are not allowed). Therefore, such one-membrane systems with complete environment are a normal form for symport/antiport P systems, and they are behaviourally equivalent (bisimulation) to multiset rewriting systems. Moreover, these systems and the related transitions preserve the properties we consider in this paper.

Due to the arguments in Note 2, we can lead the exposition of the definitions and results in this paper in terms of multiset rewriting systems only, keeping in mind that the results are equivalent both to those of the one-membrane symport/antiport model as well as even to those of multi-region systems.

2.4 Result of computations

We now proceed by defining a computation as a sequence of transitions, starting in the initial configuration, and ending in some halting configuration if it is finite. The result of a halting computation is the number of terminal objects inside the system when it halts (or the number of input objects when the system starts, in the accepting case). The set $N(\Uppi)$ of numbers generated by a multiset processing system $\Uppi$ is the set of results of all its computations. The family of number sets generated by reversible multiset rewriting systems with features α is denoted by NRMR(α) _T , where $\alpha\subseteq\{coo,inh,Pri\}$ and the braces of the set notation are omitted, with coo,  inh, and Pri meaning that we use cooperative rules, inhibitors, and priorities on the rules, respectively. Subscript T means that only terminal objects contribute to the result of computations; if T = O, we omit specifying it in the description and we then also omit the subscript T in the notation. In the case of accepting systems, we write N _a instead of N, and subscript T has no meaning. For strongly reversible systems, we replace R by R _s . For deterministic (strongly deterministic) systems, we replace R by D (D _s , respectively). In the maximally parallel case, we replace MR by OP in the notation. A subscript of OP may be used to indicate the bound on the number of membranes.

We denote the family of recursively enumerable sets of non-negative integers by NRE, and call a class of systems generating or accepting it universal. A linear number set of non-negative integers is a set S that can be defined by numbers $p_0,\,p_1, \ldots, p_k$ as $S=\left\{p_0+\sum_{i=1}^{k}n_ip_i\mid n_i\,\geq \,0,\, 1\,\leq\, i\,\leq\, k\right\}$. We denote the family of regular sets of non-negative integers (i.e., all unions of linear sets) by NREG. Clearly, linear sets are a subclass of NREG. We call a class of sets sublinear if it is a proper subclass of linear sets.

2.5 Register machines

In this paper we consider register machines with increment, unconditional decrement and test instructions, (Morita 1996), see also (Minsky 1969). An n-register machine is defined by a tuple M = (n, Q, I, q ₀, q _f ,) where n is the number of registers, I is a set of instructions bijectively labeled by elements of $Q,\,q_0\in Q$ is the initial label, and $q_f\in Q$ is the final label. The allowed instructions are:

• $(q:i?,q^{\prime},q^{\prime\prime})$—jump to instruction $q^{\prime\prime}$ if the contents of register i is zero, otherwise proceed to instruction $q^{\prime}$;

• $(q:i+,q^{\prime},q^{\prime\prime})$—add one to the contents of register i and proceed to either instruction $q^{\prime}$ or $q^{\prime\prime}$, non-deterministically;

• $(q:i-,q^{\prime},q^{\prime\prime})$—subtract one from the contents of register i and proceed to either instruction $q^{\prime}$ or $q^{\prime\prime}$, non-deterministically;

• (q _f  : halt)—terminate; it is a unique instruction with label q _f .

In the case of subtract instructions, the computation is blocked if the contents of the corresponding register is zero. Without restricting generality, we assume that a test of a register always precedes its subtraction. (In a popular model with addition and conditional subtraction instructions, reversibility would be more difficult to describe.) A configuration of a register machine is defined by the current instruction and the contents of all registers, which are non-negative integers.

If $q^{\prime}=q^{\prime\prime}$ for every instruction $(q:i+,q^{\prime},q^{\prime\prime})$ and for every instruction $(q:i-,q^{\prime},q^{\prime\prime})$, then the machine is called deterministic. Clearly, this is necessary and sufficient for the global transition (partial) mapping not to be multi-valued.

A register machine is called reversible if in the case that there is more than one instruction leading to some instruction q, then exactly two exist, they test the same register, one leads to q if the register is zero and the other one leads to q if the register is positive. It is not difficult to check that this requirement is a necessary and sufficient condition for the global transition mapping to be injective. Let us formally state the reversibility of a register machine: for any two different instructions $(q_1:i_1\alpha_1,q^{\prime}_1,q^{\prime\prime}_1)$ and $(q_2:i_2\alpha_2,q^{\prime}_2,q^{\prime\prime}_2)$, it holds that $q^{\prime}_1\neq q^{\prime}_2$ and $q^{\prime\prime}_1\neq q^{\prime\prime}_2$. Moreover,

$$ \hbox{if}\,q^{\prime}_1=q^{\prime\prime}_2\, \quad \hbox{or}\;q^{\prime\prime}_1=q^{\prime}_2,\quad\hbox{then}\, \alpha_1=\alpha_2=?\quad\hbox{and}\,i_1=i_2. $$

It has been shown (Morita 1996) that reversible register machines are universal (a straightforward simulation of, e.g., reversible Turing Machines (Bennett 1973), would not be reversible). It follows that non-deterministic reversible register machines can generate any recursively enumerable set of non-negative integers as a value of the first register by all its possible computations starting from all registers having zero value.

3 Sequential multiset rewriting

We now present a few examples to illustrate the definitions.

Example 1

Any multiset rewriting system $\Uppi_1=(O,w_0,\{u\rightarrow v\})$ with only one rule is strongly deterministic: there is no choice. Moreover, $\Uppi_1$ is strongly reversible: there is at most one incoming transition (to obtain the preimage, remove v and add u). If both w ₀ and v contain u, then no halting configuration is reachable, i.e., $\emptyset\in NR_{s}MR(coo)$. Otherwise, a singleton is generated; if w ₀ does not contain u, the computation immediately halts, hence, the singleton w ₀ is generated, i.e., $\{n\}\in NR_{s}MR(coo)$ for ${n\in\mathbb{N}}$.

Example 2

Consider the system $\Uppi_2=(\{a,b,c\},a,\{a\rightarrow ab,\,a\rightarrow c\})$. It generates the set of positive integers since the reachable halting configurations are cb ^*, and it is reversible: there is at most one incoming transition into any reachable configuration (for the preimage, replace c with a or ab with a), but not strongly reversible (e.g., aab ⇒ cab and ca ⇒ cab). Hence, ${\mathbb{N}_{+}\in NRMR(coo)}$.

Example 3

Any multiset rewriting system containing some erasing rule $u\rightarrow\lambda$ is not reversible, unless other rules are never applicable.

Example 4

Any system containing two rules of the form $x_1\rightarrow y$ and $x_2\rightarrow y$ that may apply at least one of them in some computation is not reversible.

3.1 Reversible sequential rewriting

Reversible multiset rewriting systems with either inhibitors or priorities are universal.

Theorem 1

NRMR(coo, Pri) _T  = NRMR(coo, inh) _T  = NRE.

Proof

We reduce the statement of the theorem to the claim that such multiset rewriting systems can simulate the work of any reversible register machine M = (n, Q, I, q ₀, q _f ). Consider the multiset rewriting system

$$ \begin{aligned} \Uppi&=(O,\{r_1\},q_0,R),\,\hbox{where} \\ O&=\{r_i\mid 1\leq i\leq n\}\cup Q, \\ R&=\{q\rightarrow q^{\prime}r_i,q\rightarrow q^{\prime\prime}r_i\mid (q:i+,q^{\prime},q^{\prime\prime})\in I\} \\ &\quad\cup\{qr_i\rightarrow q^{\prime}, qr_i\rightarrow q^{\prime\prime}\mid (q:i-,q^{\prime},q^{\prime\prime})\in I\}\cup R_t, \\ R_t&=\{q\rightarrow q^{\prime\prime}|_{\neg r_i},qr_i\rightarrow q^{\prime}r_i\mid (q:i?,q^{\prime},q^{\prime\prime})\in I\}.\\ \end{aligned} $$

Inhibitors can be replaced by priorities by redefining R _t as follows:

$$ R_{t}=\{qr_i\rightarrow q^{\prime}r_i>q\rightarrow q^{\prime\prime}\mid (q:i?,q^{\prime},q^{\prime\prime})\in I\}. $$

There is a bijection between the configurations of $\Uppi$ containing one symbol from Q and the configurations of M, so reversibility of $\Uppi$ follows from the correctness of the simulation, the reversibility of M and because the number of symbols from Q is preserved by the transitions of $\Uppi$.    $\square$

The universality in Theorem 1 leads to the following undecidability.

Corollary 1

Let $\mathcal{P}_1\,(\mathcal{P}_2)$ be the class of multiset rewriting systems with inhibitors (with priorities, respectively). Reversibility is undecidable for $\mathcal{P}_1\,({\cal P}_2)$.

Proof

Recall that the halting problem for register machines is undecidable. Add instructions $q_f\rightarrow F_1,\,q_f\rightarrow F_2,\,F_1\rightarrow F,\,F_2\rightarrow F$ to the construction presented above (F ₁, F ₂, F are new objects); now the system is non-reversible if and only if some configuration containing F is reachable, i.e., if the underlying register machine does not halt, which is undecidable.    $\square$

3.2 Strong reversibility

Deciding strong reversibility is much easier: it is necessary and sufficient that no two different rules are applicable to any configuration. Without restricting generality we only consider systems without useless rules, e.g., no rule is inhibited by some of its reactants (i.e., by objects in the left-hand side of the rule).

Consider the case that inhibitors may be used, and let $r_1:x_1\rightarrow y_1v$ and $r_2:x_2\rightarrow y_2v$ be two rules of the system (possibly controlled by inhibitors), where v is the largest common submultiset of the right-hand sides of r ₁ and r ₂. Then both rules can be reversely applied to some configuration C if and only if it contains y ₁ v and y ₂ v and none of these two rules is inhibited. Now writing C as y ₁ y ₂ vw, we get the two possible transitions x ₁ y ₂ w ⇒ y ₁ vy ₂ w and x ₂ y ₁ w ⇒ y ₂ vy ₁ w. The inhibitors should in particular forbid one of these transitions in the case w = λ (from that, the general case for w follows immediately). Therefore, either r ₁ should be inhibited by some object from y ₂, or r ₂ should be inhibited by some object from y ₁. Clearly, this criterion is also sufficient, since for any two rules the competition for the backwards applicability is solved by inhibitors. We have just proved the following statement:

Theorem 2

A sequential multiset rewriting system with inhibitors is strongly reversible if for any two rules r ₁ and r ₂, either r ₁ is inhibited by $rhs(r_2)\setminus rhs(r_1)$ or r ₂ is inhibited by $rhs(r_1)\setminus rhs(r_2).$

The case of priorities is slightly more involved. Let $r_1:x_1\rightarrow y_1v$ and $r_2:x_2\rightarrow y_2v$ be two rules of the system, where v is the largest common submultiset of the right sides of r ₁ and r ₂. Then both rules can be reversely applied to some configuration C if and only if it contains y ₁ y ₂ v and none of these two rules is made inapplicable by rules of higher priority. Writing C as y ₁ y ₂ vw, we get the possible transitions x ₁ y ₂ w ⇒ y ₁ vy ₂ w and x ₂ y ₁ w ⇒ y ₂ vy ₁ w. The priorities should in particular forbid one of these transitions in the case w = λ (from that, the general case for w follows immediately). Therefore, either r ₁ should be made inapplicable by some rule r > r ₁ with left-hand side contained in x ₁ y ₂, or r ₂ should be made inapplicable by some rule r > r ₂ with left-hand side contained in x ₁ y ₂. Clearly, this criterion is also sufficient since the competition for reverse applicability between any two rules is eliminated. We have just proved the following result:

Theorem 3

A sequential multiset rewriting system with priorities is strongly reversible if for any two rules r ₁, r ₂ there exists a rule r such that either r > r ₁ and $lhs(r)\subseteq lhs(r_1)(rhs(r_2)\setminus rhs(r_1)$ or r > r ₂ and $lhs(r)\subseteq lhs(r_2)(rhs(r_1)\setminus rhs(r_2).$

It is not difficult to see that the criterion of strong reversibility for systems that may use both inhibitors and priorities is obtained as a disjunction of the requirements from Theorem 2 and Theorem 3 for any two rules r ₁ and r ₂.

Corollary 2

A sequential multiset rewriting system with priorities is strongly reversible if for any two rules r ₁ and r ₂ at least one of the following conditions holds:

• r ₁ is inhibited by $rhs(r_2)\setminus rhs(r_1),$

• r ₂ is inhibited by $rhs(r_1)\setminus rhs(r_2),$

• there exists a rule r > r ₁ such that $lhs(r)\subseteq lhs(r_1)(rhs(r_2)\setminus rhs(r_1),$

• there exists a rule r > r ₂ such that $lhs(r)\subseteq lhs(r_2)(rhs(r_1)\setminus rhs(r_2).$

Corollary 3

A multiset rewriting system without control is strongly reversible if and only if it only has exactly one rule.

$$ NR_{s}MR(coo)_{T}=\{\emptyset \}\cup \{\{n\}\mid n\in {\mathbb{N}}\}. $$

It is known that (see, e.g., Freund et al. 2005) the generative power of sequential multiset rewriting systems equals PsMAT, even without requiring additional properties like reversibility.

Corollary 4

Reversible multiset rewriting systems without priorities and without inhibitors are not universal.

It is an open problem to specify the exact generative power of this class.

We now return to controlled systems. Surprisingly, adding priorities turns degenerate computational systems into universal ones.

Theorem 4

NR _s MR(coo, Pri) _T  = NRE.

Proof

Consider the construction from Theorem 1, for the case of priorities. Further, add rules R _d (q and $q^{\prime}$ may also be the same):

$$ R_{d}=\{qq^{\prime}\rightarrow qq^{\prime}\mid q,q^{\prime}\in Q\}. $$

Finally, extend the priority relation to a total order relation in such a way that every rule from R _d has priority over every rule not from R _d . Such a system remains universal, because throughout the simulation of register machines, exactly one object from Q is present, and rules from R _d are not applicable; for the same reason, rules with different states in the left-hand side are never applicable simultaneously, so the extension of the priority relation has no effect on the simulation.

The obtained system is also strongly reversible. Indeed, all rules preserve the number of objects from Q. All configurations without objects from Q are immediately halting and have no preimage. Any configuration with multiple objects from Q evolves into itself (by applying a rule with the highest priority possible, trivially rewriting two state symbols), and its preimage is just the configuration itself, with the incoming transition corresponding to the applicable rule with the highest priority. In case of one object from Q, the property follows from the strong reversibility of the simulated register machine.    $\square$

3.3 Deterministic sequential rewriting

The concept of determinism common to multiset rewriting systems as considered in the area of membrane computing essentially means that such a system, starting from any fixed configuration, has a unique computation. As it will be obvious later, this property is often not decidable. Of course, this section only deals with accepting systems.

First, it is well known that deterministic multiset rewriting systems with either priorities or inhibitors are universal, by simulating of any (deterministic accepting) register machine M. In fact, in this case the construction of Theorem 1 is both deterministic and reversible.

Corollary 5

N _a D _s MR(coo, Pri) _T  = NRE.

Proof

To get a strongly deterministic system, it suffices to take the construction with priorities in Theorem 1 (simulating any deterministic accepting register machine) and to extend the priorities to a total order relation. The total order relation can be defined by the relation specified by taking the union of the relation of R _t and the relation induced by an arbitrary fixed (e.g., lexicographical) order on the objects from Q as they appear in the left-hand sides of rules.    $\square$

In general, if a certain class of non-deterministic systems is universal even in a deterministic way, then the determinism is undecidable for that class. This applies to multiset rewriting systems, similarly to Corollary 1.

Corollary 6

Let $\mathcal{P}_1\,(\mathcal{P}_2)$ be the class of multiset rewriting systems with inhibitors (with priorities, respectively). Determinism is undecidable for $\mathcal{P}_1\,({\cal P}_2).$

Proof

For an arbitrary register machine M, there is a deterministic multiset rewriting system $\Uppi$ with either inhibitors or priorities simulating M. Without restricting generality we assume that an object q _f appears in the configuration of $\Uppi$ if and only if it halts. Add instructions $q_f\rightarrow F_1$ and $q_f\rightarrow F_2$ to the set of rules (F ₁, F ₂ are new objects); now the system is non-deterministic if and only if some configuration with q _f is reachable, i.e., when M does not halt, which is undecidable. $\square$

3.4 Strong determinism

The strong determinism we now consider means that a system has no choice of transitions from any configuration. We now claim that (unlike the non-strong case) this is a syntactic property.

Theorem 5

A multiset rewriting system is strongly deterministic if and only if any two rules are either mutually excluded by an inhibitor (of one rule appearing on the left-hand side of another rule), or are in a priority relation.

Proof

Any multiset rewriting system with exactly one rule is strongly deterministic.

The forward implication of the theorem holds because mutually excluding reactant/inhibitor conditions eliminate all competing rules except one, and so does the priority relation. In the result, for any configuration at most one rule is applicable.

Conversely, assume that two rules p and $p^{\prime}$ of the system are not in a priority relation, and are not mutually excluded by the reactant/inhibitor conditions. Let x and $x^{\prime}$ be the multisets of objects consumed by the rules p and $p^{\prime}$, respectively. Then, to the configuration $C=xx^{\prime}$, it is possible to apply either rule, causing contradiction to the condition of strong determinism.    $\square$

Corollary 7

A multiset rewriting system without inhibitors and without priority is not strongly deterministic, unless it only has exactly one rule.

We now characterize the power of strongly deterministic multiset rewriting systems without additional control: any multiset rewriting system without inhibitors or priorities accepts either the set of all non-negative integers, or a finite set of all numbers bounded by some number.

Theorem 6

$$ \begin{aligned} N_aD_sMR(coo)&=\{\emptyset,{\mathbb{N}}\}\\ &\quad\cup\{\{k\mid 0\leq k\leq n\}\mid n\in {\mathbb{N}}\}. \end{aligned} $$

Proof

Any strongly deterministic system is of the form $(O,T,w_0,\{u\rightarrow v\})$. If u is not contained in v, then the system accepts all numbers. Otherwise, if v contains u, the computation starting from an initial configuration C is not accepting if and only if u is contained in both C and v. Hence, the system accepts all numbers k for which there exists an $x\in \Upsigma ^{k}$ such that w ₀ x does not contain the multiset u. The converse of the latter condition is monotone with respect to k, i.e., it is either never satisfied, or always satisfied, or there exists a number $n\in N$ such that it holds if and only if k > n.

• System ({a}, {a}, a, $\{a\rightarrow a\})$ accepts the empty set $\emptyset$, because the computation from any configuration aw with $w\in a^{*}$ is an infinite loop;

• system $(\{a\},\{a\},\lambda,\{a\rightarrow\lambda\})$ accepts ${\mathbb{N}}$, i.e., any natural number, because it halts after erasing everything in n steps when starting with a ⁿ, for any ${n\in\mathbb{N}}$; and

• for any ${n\in\mathbb{N}}$ there is a system $(\{a\},\{a\},\lambda,\{a^{n+1}\rightarrow a^{n+1}\})$ accepting $\{k\mid 0\leq k\leq n\}$, because the system immediately halts in the initial configuration if and only if the input does not exceed n, and enters an infinite loop otherwise.

These examples show the converse implication of the theorem.    $\square$

Theorem 6 shows that the computational power of strongly deterministic sequential multiset rewriting systems without additional control is, in a certain sense, degenerate (it is sublinear). We now strengthen Theorem 6 from strongly deterministic systems to all deterministic ones.

Corollary 8

$$ \begin{aligned} N_aDMR(coo)&=\{\emptyset,{\mathbb{N}}\}\\ &\quad\cup\{\{k\mid 0\leq k\leq n\}\mid n\in {\mathbb{N}}\}. \end{aligned} $$

Proof

Like in Theorem 6, the system accepts all numbers k for which there exists $x\in\Upsigma^k$ such that the computation starting from w ₀ x halts. It suffices to recall that if $C\subseteq C^{\prime}$ and a computation starting with $C^{\prime}$ halts, then a computation starting with C also halts. Indeed, since the computation starting from $C^{\prime}$ is deterministic, if it applies rule r in step s, then the computation starting from C cannot apply any other rule in the same step. The corresponding configurations of the two computations preserve any $\subseteq$ relation of the initial configurations. $\square$

4 Maximally parallel multiset rewriting

We now present a few examples to illustrate the definitions when the rules are applied in parallel.

Example 5

Consider the P system $\Uppi_0=(\{a,b\},a,\{a\rightarrow ab\})$. It is strongly reversible: there is at most one incoming transition (for a preimage, remove as many copies of b as there are copies of a, in case it is possible and there is at least one copy of a), but no halting configuration is reachable. Therefore, $\emptyset\in NR_{s}OP_1(ncoo)$.

Example 6

Consider the P system $\Uppi_1=(\{a,b,c\},a,\{a\rightarrow ab,\, a\rightarrow c\})$. As the corresponding sequential multiset rewriting system, it generates the set of positive integers since the reachable halting configurations are cb ^*, and it is reversible because there is at most one incoming transition into any reachable configuration (for the preimage, replace c with a or ab with a), but not strongly reversible (e.g., aa ⇒ cc and ac ⇒ cc). Hence, ${\mathbb{N}_{+}\in NROP_1(ncoo)}$.

Example 7

Consider the P system $\Uppi_2=(\{a,b\},aa,\{aa\rightarrow ab,\, ab\rightarrow bbb\})$. It is reversible (the configuration aa has in-degree 0, while the configurations ab and bbb have in-degree 1, and no other configuration is reachable), but not strongly reversible (e.g., aab ⇒ abbb and aabb ⇒ abbb).

Example 8

Any P system containing a rule $x\rightarrow \lambda$ is not reversible. Therefore, erasing rules cannot be used in reversible P systems.

Example 9

Any P system containing two rules $x_1\rightarrow y$ and $x_2\rightarrow y$ such that at least one of them can be applied in some computation is not reversible.

4.1 Reversible parallel rewriting

The following result can be obtained by a construction identical to that in Theorem 1. Indeed, notice that every rule uses some symbol associated to Q, and there is exactly one such symbol present in the system all the time, so multiple rules are never applied in the same step.

Theorem 7

NROP ₁(coo, Pri) _T  = NROP ₁(coo, inh) _T  = NRE.

These universality results lead to the following undecidability results (by a construction identical to that in Corollary 1):

Corollary 9

Let $\mathcal{P}_3\,(\mathcal{P}_4)$ be the class of P systems with inhibitors (with priorities, respectively). Reversibility is undecidable for $\mathcal{P}_3\,(\mathcal{P}_4).$

The construction in Theorem 1 uses both cooperation and additional control. It is natural to ask whether both inhibitors and priorities can be avoided. Yet, consider the following situation: let $(p:i?,s,q^{\prime\prime}),(q:i?,q^{\prime},s)\in I$. It is not unusual for reversible register machines to have this, since the preimage of a configuration containing a representation of instruction s depends on register i. Nevertheless, P systems with maximal parallelism without additional control can only implement a zero-test by a try-and-wait-then-check strategy. In this case, the object containing the information about the register p finds out the result of checking after a possible action of the object related to the register. Therefore, when the instruction represented in the configuration of the system changes to s, it obtains an erroneous preimage representing instruction q. This leads us to the following

Conjecture 1

Reversible P systems without priorities and without inhibitors are not universal.

4.2 Strong reversibility

Unlike reversibility itself, the more restricted property of strong reversibility is decidable, see (Ibarra 2011), since checking that at most one incoming transition exists for any configuration is no longer related to reachability.

However, the following theorem establishes a very serious limitation on such systems if no additional control is used.

Theorem 8

In strongly reversible P systems without inhibitors and without priorities, every configuration is either halting or induces only infinite computation(s).

Proof

If the right-hand side of every rule contains the left-hand side of some rule, then the claim obviously holds (only infinite computations if at least one rule is applicable to the initial configuration, otherwise no transition is possible and the computation immediately halts). On the other hand, assume $x\rightarrow y$ to be a rule of the system such that y does not contain the left-hand side of any rule (hence, x ≠ y, too). Then x ⇒ y and y is a halting configuration. It is not difficult to see that then two different preimages of yy exist, i.e., xy ⇒ yy (the objects in y are idle) and xx ⇒ yy (the rule can be applied twice). Therefore, such a system is not strongly reversible, which proves the theorem. $\square$

Thus, the strongly reversible systems without additional control can only generate singletons, and only in a degenerate way, i.e., without doing any transition step:

Corollary 10

${NR_sOP_1(coo)_T=\{\{n\}\mid n\in\mathbb{N}\}.}$

It turns out that the theorem above does not hold if inhibitors are used: consider the system $\Uppi_{4}=(\{q,f,a\},q,\{q\rightarrow qaa|_{\neg f}\},\{q\rightarrow f|_{\neg f}\})$. If at least one object f is present or no objects q are present, a configuration of $\Uppi_{4}$ is a halting one. Otherwise, all objects q are used by the rules of the system. Therefore, the only possible transitions in the space of all configurations are of the form q ^m+n a ^p−2m ⇒ q ^m f ⁿ a ^p,  m + n > 0,  p ≥ 2m and the system is strongly reversible. Notice that $N(\Uppi _{4})=\{2k+1\mid k\geq 0\}$, since, in any halting computation, starting from q we apply the first rule for k ≥ 0 steps and finally the second rule.

We now consider the controlled case. Once again, priorities change degenerate computational systems into universal ones.

Theorem 9

NR _s OP ₁(coo,Pri) _T  = NRE.

Proof

Consider the construction from Theorem 4. We recall that every rule uses at least one object from Q and preserves the number of objects from Q. When there are no multiple objects from Q in the system, multiple rules cannot be applied simultaneously, so the behaviour is identical for the maximally parallel case, and the simulation is correct. Otherwise, due to the total priority, only the rule with the highest possible priority (rewriting two state symbols into themselves) will be applied, as many times as possible, yielding the same configuration. Hence, the only preimage of a configuration in this case is the configuration itself (and the only incoming transition consists of the maximal application of the rule with the highest priority among the applicable ones), hence, the same system is reversible in the maximally parallel case, too. $\square$

Remark 1

Notice that universality may still be obtained by simulating priorities, if the concept of inhibitors is generalized as follows: typically, inhibitors are defined as single objects. Occasionally, in P systems literature one considers inhibitors that are multisets, in the sense that the rule is applicable if the inhibiting multiset is not a submultiset of the current configuration. A further possible generalization would be for a rule to have multiple inhibiting multisets, in the sense that the rule is applicable if it is not inhibited by any of these multisets, i.e., if none of them is a submultiset of the current configuration.

For instance, a rule $a\rightarrow b|_{\neg cd,\neg ce}$ would be applicable to an object a if the current configuration does not simultaneously contain c and d, and also does not simultaneously contain c and e. Indeed, priorities can then be simulated by including as inhibiting multisets the left-hand sides of all rules with higher priorities.

We conjecture that strongly reversible universality is impossible using just one singleton inhibitor in any rule. This remark also holds for the sequential case.

4.3 Strongly deterministic parallel rewriting

The concept of determinism common to membrane computing essentially means that such a system, starting from the fixed configuration, has a unique computation. As it will be obvious later, this property often is not decidable. Of course, this section only deals with accepting systems.

First, we recall that if deterministic accepting register machines are simulated in Theorem 7, then the construction is both deterministic and reversible. The following corollary is obtained in an analogous way as Corollary 5, i.e., by extending the priority relation to a total order.

Corollary 11

N _a D _s OP ₁(coo,Pri) _T  = NRE.

In general, if a certain class of non-deterministic P systems is universal even in a deterministic way, then the determinism is undecidable for that class. This also applies to the special model of P systems considered in this paper (the proof is similar to that of Corollary 6).

Corollary 12

Determinism is undecidable for the class of P systems.

On the contrary, the strong determinism we now consider means that a system has no choice of transitions from any configuration. We claim that it is a syntactic property; to formulate the claim, we need the following notions: the domain of a rule $x\rightarrow y,\,x\rightarrow y|_{a}$ or $x\rightarrow y|_{\neg a}$ is the set of objects in x (the multiplicities of objects in x are not relevant for the results in this paper). We say that two rules are mutually excluded by promoter/inhibitor conditions if the inhibitor of one is either the promoter of the other rule, or is in the domain of the other rule.

Theorem 10

A P system is strongly deterministic if and only if any two rules with intersecting domains are either mutually excluded by promoter/inhibitor conditions, or are in a priority relation.

Proof

Clearly, any P system with only one rule is strongly deterministic, because the degree of parallelism is defined by exhausting the objects from the domain of this rule.

The forward implication of the theorem holds because the rules with non-intersecting domains do not compete for the objects, while mutually excluding promoter/inhibitor conditions eliminate all competing rules except one, and so does the priority relation. As a result, for any configuration the set of objects is partitioned in disjoint domains of applicable rules, and the number of applications of different rules can be computed independently.

We now proceed with the converse implication. Assume that two rules p and $p^{\prime}$ of the system intersect in the domain, but are not in a priority relation and are not mutually excluded by the promoter/inhibitor conditions. Let x and $x^{\prime}$ be the multisets of objects to be rewritten by the rules p and $p^{\prime}$, respectively. Then consider the multiset C which is the minimal multiset including x and $x^{\prime}$, and the configuration $C^{\prime}$, defined as the minimal multiset including $C^{\prime}$ and the promoters of p and $p^{\prime}$, if any.

Starting from $C^{\prime}$, there are enough objects for applying either p or $p^{\prime}$. Since the rules neither are mutually excluded nor are in a priority relation, both rules are applicable. However, both cannot be applied together because the rules intersect in the domain and thus the multiset C is strictly included in $xx^{\prime}$ (and $C^{\prime}$ is only different from C if a promoter of p or $p^{\prime}$ does not belong to C). In that way we get a contradiction to the definition of strong determinism and therefore prove the sufficiency of the condition stated in the theorem. $\square$

Corollary 13

A P system without promoters, inhibitors, and without priority is strongly deterministic if and only if the domains of all rules are disjoint.

We now show an interesting property of strongly deterministic P systems without additional control. To define it, we use the following notion for deterministic P systems: let $C\Rightarrow\,^{\rho _1}C_1\Rightarrow\,^{\rho _2}C_2\ldots\,\Rightarrow^{\rho _{n}}C_{n}$, where ρ _i are multisets of applied rules, 1 ≤ i ≤ n. We define the multiset of rules applied starting from configuration C in n steps as

$$ m(C,n)=\bigcup_{i=1}^{n}\rho _i. $$

We write $lhs(x\rightarrow y)=x$ and $rhs(x\rightarrow y)=y$, and extend this notation to the multiset of rules by taking the union of the corresponding multisets. For instance, if C ⇒ ^ρ C ₁, then $C_1=(C\setminus lhs(\rho)\cup rhs(\rho)$.

Lemma 1

Consider a strongly deterministic P system $\Uppi$ without promoters, inhibitors and without priorities as well as two configurations $C,C^{\prime}$ with $C\,\subsetneq\, C^{\prime}$ and a number n; then $m(C,n)\subseteq m(C^{\prime},n).$

Proof

We prove the statement by induction. It holds for n = 1 step because strongly deterministic systems are deterministic, and if the statement did not hold, then the system even would not be deterministic.

Assume the statement holds for n − 1 steps, and

$$ \begin{aligned} &C\Rightarrow\, ^{\rho _1}C_1\Rightarrow\, ^{\rho _2}C_2{\cdots}\Rightarrow\, ^{\rho _{n}}C_{n}, \\ &C^{\prime}\Rightarrow\,^{\rho^{\prime}_1}C^{\prime}_1 \Rightarrow\,^{\rho^{\prime}_2}C^{\prime}_2{\cdots} \Rightarrow\,^{\rho^{\prime}_n}C^{\prime}_n. \end{aligned} $$

Then, after n − 1 steps the difference between the configurations can be described by $C^{\prime}_{n-1}=(C_{n-1}\setminus D_0)\cup D_1\cup D_2$, where

• $D_0=lhs(m(C^{\prime},n-1)\setminus m(C,n-1))$,

• $D_1=rhs(m(C^{\prime},n-1)\setminus m(C,n-1))$,

• $D_2=C^{\prime}\setminus C$,

Therefore, $C^{\prime}_{n-1}\setminus C_{n-1}\subsetneq D_0$. Because of the strong determinism property, these objects will either be consumed by some rules from $m(C^{\prime},n-1)\setminus m(C,n-1)$, or remain idle. Therefore, $m(C_{n-1},1)\subseteq m(C^{\prime}_{n-1},1)\cup (m(C^{\prime},n-1)\setminus m(C,n-1)$. It follows that $m(C,n)\subseteq m(C^{\prime},n)$, thus concluding the proof. $\square$

Example 10

For the P system $\Uppi=(\{a\},a,\{p:a^{3}\rightarrow a\})$, for example we get

$$ \begin{aligned} C&=a^{15}\Rightarrow^{p^{5}}a^{5}\Rightarrow^{p}a^{3}\Rightarrow^{p}a,\\ C^{\prime}&=a^{14}\Rightarrow^{p^{4}}a^{6}\Rightarrow^{p^2}a^2, \end{aligned} $$

i.e., $m(C^{\prime},n)=p^{6}\subset p^{7}=m(C,n).$

We now characterize the power of strongly deterministic P systems without additional control: any P system without promoters, inhibitors or priorities accepts either the set of all non-negative integers, or a finite set of all numbers bounded by some number.

Theorem 11

$$ \begin{aligned} N_aD_sOP_1(coo)&=\{\emptyset,{\mathbb{N}}\}\\ &\quad\cup \{\{k\mid 0\leq k\leq n\}\mid n\in {\mathbb{N}}\}. \end{aligned} $$

Proof

A computation starting from a configuration C is not accepting if it does not halt, i.e., if $\lim_{n\rightarrow \infty }m(C,n)=\infty$. Due to Lemma 1, if the computation starting from C is accepting, then any computation starting from a submultiset $C^{\prime}\subseteq C$ is accepting, too. This also implies that if the computation starting from C is not accepting, then neither is any computation starting from a multiset containing C. Therefore, the set of numbers accepted by a strongly deterministic P system without additional control can be identified by the largest number of input objects leading to acceptance, unless the system accepts all numbers or none.

The converse can be shown by the following P systems.

• System $(\{a\},\{a\},a,\{a\rightarrow a\})$ accepts $\emptyset$, because with any input the only computation is an infinite loop;

• system $(\{a\},\{a\},\lambda,\{a\rightarrow\lambda\})$ accepts ${\mathbb{N}}$, i.e., anything, because with any input it halts after erasing everything in one step; and

• for any ${n\in\mathbb{N}}$ there is a system $(\{a\},\{a\},\lambda,\{a^{n+1}\rightarrow a^{n+1}\})$ accepting $\{k\mid 0\leq k\leq n\}$, because the system halts with the initial configuration if and only if the input does not exceed n, and enters an infinite loop otherwise. $\square$

Theorem 11 shows that the computational power of strongly deterministic P systems without additional control is, in a certain sense, degenerate (it is subregular). We now show that the use of promoters and inhibitors leads to universality of even the strongly deterministic P systems.

Theorem 12

N _a D _s OP ₁(coo, pro, inh) = NRE.

Proof

We reduce the statement of the theorem to the claim that such P systems simulate the work of any deterministic register machine M = (n, Q, I, q ₀, q _f ). Without restricting generality, we assume that every subtracting instruction is preceded by the corresponding testing instruction. Consider a P system

$$ \begin{aligned} \Uppi&=(O,\{r_1\},q_0,R),\,\hbox{where} \\ O&=\{r_i,d_i\mid 1\leq i\leq n\}\cup\{q,q_1\mid q\in Q\}, \\ R&=\{q\rightarrow q^{\prime}r_i\mid (q:i+,q^{\prime},q^{\prime})\in I\} \\ &\quad\cup \{q\rightarrow q_1d_i,q_1\rightarrow q^{\prime},\, d_ir_i\rightarrow\lambda\mid (q:i-,q^{\prime},q^{\prime})\in I\} \\ &\quad\cup \{q\rightarrow q^{\prime}|_{r_i},q\rightarrow q^{\prime\prime}|_{\neg r_i}\mid (q:i?,q^{\prime},q^{\prime\prime})\in I\}. \\ \end{aligned} $$

All rules using objects q and $q^{\prime}$ have disjoint domains, except the ones in the last line, simulating the zero/non-zero test. However, they exclude each other by the same object which serves as promoter and inhibitor, respectively. Subtraction of register i is handled by producing object d _i , which will “annihilate” (i.e., be deleted together with) r _i . Therefore, different instructions subtracting the same r _i are implemented by the same rule $d_ir_i\rightarrow \lambda$, hence all rules using objects d _i and r _i have different domains. It follows from Theorem 10 that the system is strongly deterministic, which observation concludes the proof. $\square$

Remark 2

In the theorem stated above, both promoters and inhibitors were used to eliminate conflicts between the rules for the zero test and for the positive test. By the reasons already explained in Remark 1, universality may be obtained by simulating priorities, if the inhibitors are generalized to multiple multisets.

Notice that, since (unlike in the case of strong reversibility) no inhibiting multiset contains multiple copies of the same symbol, the condition of applicability is a function defined on the signature of the configuration, i.e., it does not depend on the multiplicities; it is a conjunction of disjunctions of effects of atomic inhibitors (e.g., for a rule $a\rightarrow b|_{\neg cd,\neg ce}$, such a condition is $(\neg c\vee \neg d)\wedge (\neg c\vee \neg e)$).

We conjecture that strongly deterministic universality is impossible using just one singleton inhibitor in any rule (with or without promoters). This remark also holds for the sequential case.

5 Conclusions

We have outlined the concepts of reversibility, strong reversibility, determinism, and strong determinism for sequential and maximally parallel multiset rewriting systems and established the following results for the computational power of such systems, see Table 1:

Table 1 The power of sequential multiset rewriting systems with different properties, depending on the features (top), and the parallel case (bottom)

Sequential and maximally parallel multiset rewriting systems with priorities have shown to be universal for all four properties, i.e., for reversibility, strong reversibility, determinism, and strong determinism, whereas without control only deterministic maximally parallel systems are universal and all others are even sublinear except for the reversible classes (in the case of sequential systems, we have shown non-universality, for maximally parallel systems we have not been able to prove such a conjecture yet).

With inhibitors, deterministic and reversible systems are universal in both cases, too, whereas for strong determinism universality could only be shown for maximally parallel systems with inhibitors and promoters (which are of no use in the sequential case). All other remaining classes are conjectured to be non-universal.

Strongly reversible sequential multiset rewriting systems without control do not halt unless the starting configuration is halting, but this is no longer true with inhibitors. For systems with inhibitors or priorities, strong reversibility has also been characterized syntactically; moreover, we have given a syntactic characterization for the property of strong determinism. For sequential systems without control, the power of deterministic systems coincides with that of strongly deterministic systems: such a system without control either accepts all natural numbers, or a finite set of numbers; a similar result holds for strongly deterministic maximally parallel systems.

We repeat some interesting differences of the sequential case with respect to the parallel case:

• promoters are useless;

• the criterion of strong determinism is different;

• the criterion of strong reversibility is not only decidable, but has a concrete description and thus is easily testable;

• the power of deterministic uncontrolled systems is radically different: sublinear instead of universal.

Characterizing determinism and especially reversibility for systems with intermediate parallelism between sequential and maximally parallel cases remains an open research area.