On Parallel Array P Systems

On Parallel Array P Systems Linqiang Pan1, Gheorghe P˘aun2 1Key Laboratory of Image Processing and Intelligent Control School of Automation Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania [email protected], [email protected] Summary. We further investigate the parallel array P systems recently introduced by K.G. Subramanian, P. Isawasan, I. Venkat, and L. Pan. We first make explicit several classes of parallel array P systems (with one or more axioms, with total or maximal parallelism, with rules of various types). In this context, some results from the above mentioned paper by Subramanian et al. are improved. A series of open problems are formulated. 1 Introduction The generality/versatility of membrane computing is already a well known fact, the computing framework abstracted from the cell structure and functioning can cover a large variety of processes, dealing – in particular – with a large variety of objects processed in the compartments of membrane structures. The arrays (in general, 2D and 3D figures of various types) are one of the types of objects considered already since 2001, see [3]. A direct extension from string objects to two-dimensional arrays was introduced in [1] and then investigated in a series of papers. A recent contribution to this research area is [6], where a natural counterpart of the array P systems from [1] is considered: parallel rewriting of arrays, instead of the sequential rewriting from [1]. Actually, the kind of parallelism investigated in [6] is that suggested by Lindenmayer systems: all nonterminals of an array should be rewritten in each step. A possible alternative, closer to the style of membrane computing, is to consider the maximal parallelism: a multiset of rules is used which is maximal among the multisets of applicable rules in a given moment. In the present paper, we explicitly consider these two kinds of parallelism, and we prove that most of the results from [6] hold true for both kinds of parallelism, 294 L. Pan, Gh. Paun also improving those results (less membranes are used in some of them, while the powerful priority relation is avoided in other results). Several questions remain open; several topics for further research are formulated. 2 Definitions and Notations It is useful for the reader to be familiar with basic elements of membrane computing, e.g., from [4] (with up-dated information available at [7]), and of array grammars, but the used notions will be recalled below. Actually, in what concerns the arrays, we will usually use the pictorial representation, hence we need a minimal formalism (otherwise, cumbersome if rigorously formulated). The arrays we consider consist of finitely many symbols from a specified alphabet Vplaced in the points (we call them pixels) of Z2(the plane); the points of the plane which are not marked with elements of Vare supposed to be marked with the blank symbol #/∈V. Given an array Wover V,supp(W) denotes the set of points in Z2marked with symbols in V. In order to specify an array, it is usual to specify the pixels of the support, by giving their coordinates, together with their associated symbols from V, but, as we said above, we will pictorially represent the arrays, indicating their non-blank pixels. These pictures should be interpreted as arrays placed in any position of the plane (congruent, possible to be superposed by means of a translation). We denote by V∗2the set of all two-dimensional arrays of finite support over V, including the empty array, denoted by λ. Any subset of V∗2is called an array language. We handle the arrays by means of rewriting rules. An array rewriting rule (over an alphabet V) is written as a usual string rewriting rule, in the form W1→W2, where W1, W2are isotonic arrays over V:W1and W2cover the same pixels, no matter whether they are marked with symbols in Vor with #. When graphically representing an array, usually we ignore the blank pixels, but, when representing rewriting rules, the pixels marked with # are also explicitly shown. A rule as above is used to rewrite an array Win the natural way: a position in Wis identified where W1can be superposed, with all pixels matching, whether or not they are marked with symbols in Vor with #, and then those pixels are replaced with W2 (the fact that W1and W2are isotonic ensures the fact that this replacement is possible). If the result is the array W′, we write W=⇒W′. The reflexive and transitive closure of the relation =⇒is denoted by =⇒∗. Similar to string rewriting rules, the array productions can be classified according to their form. We consider here only two types of rules, context-free and regular. Remember that all rules we work with are isotonic (the shapes of the left hand side and the right hand side are identical, only the marking, by blank or non-blank symbols, differs). Thus, a context-free rule is an isotonic one with only one non-blank pixel in its left hand side. On Parallel Array P Systems 295 Note that we have not distinguished between terminal and nonterminal symbols, like in Chomsky grammars; for regular rules we need such a distinction. Thus, a regular rule over the alphabets Tand N,Nbeing the nonterminal one, is a rule of one of the following forms: A#→a B, #A→B a, # A→B a,A #→a B, A → B, A →a, where A, B ∈Nand a∈T. Because in what follows we work, like in [6], in a Chomsky framework, with terminal and nonterminal symbols, we also impose that in a context-free rule the single non-blank pixel in the left hand side is marked with a nonterminal symbol. Before introducing the array P systems, we recall a notion useful below: twodimensional right-linear grammars. Such a grammar [2] is a construct G= (Vh, Vv, Vi, T, S, Rh, Rv), where Vh, Vv, Vi are the horizontal, vertical, and intermediate alphabets of nonterminals, Vi⊆Vv, Tis the terminal alphabet, S∈Vhis the axiom, Rhis the finite set of horizontal rules, of the forms X→AY, X →A, for X, Y ∈Vh, A ∈Vi, and Rvis the finite set of vertical rules, of the forms A→aB, A →a, for A, B ∈Vv, a ∈T. A derivation in Ghas two phases, an horizontal one, which uses rules from Rh, and a vertical one, which uses rules from Rv. The horizontal derivation is as usual in a string grammar. In the vertical phase, the rules are used in parallel, downwards, with the restriction that the terminal rules are used simultaneously for all vertical nonterminals. Thus, in the end, a rectangle is obtained, filled with symbols in T. The set of all rectangles generated in this way by Gis denoted by L(G) and the family of all languages of this form is denoted by 2RLG. Two array languages which will be used below are LR, of all hollow rectangles with the edges marked with a(one element of this language is shown in Fig. 1), and LS, of all hollow squares with the edges marked with a. aaaaaaaaa a a a a a a aaaaaaaaa Fig. 1. A hollow rectangle in LR. 3 Parallel Array P Systems We pass now to define the parallel array P systems. Such a device (of degree m≥1) is a construct Π= (V, T, #, µ, F1, . . . , Fm, R1, . . . , Rm, io), where: Vis the total alphabet, T⊆Vis the terminal alphabet, # is the blank symbol, µis a membrane structure with mmembranes labeled in a one-to-one way 296 L. Pan, Gh. Paun with 1,2, . . . , m,F1, . . . , Fmare finite sets of arrays over Vassociated with the m regions of µ,R1, . . . , Rmare finite sets of array rewriting rules over Vassociated with the mregions of µ; the rules have attached targets here, out, in (in general, here is omitted), hence they are of the form W1→W2(tar); finally, iois the label of a membrane of µspecifying the output region. In what follows, we only consider array P systems with regular (REG) and context-free (CF) rules – with the symbols in V−Tconsidered as nonterminals. A computation in an array P system is defined in the same way as in a symbol object P system, with the following details. Each array from a compartment of the system must be rewritten by the rules in that compartment. The rewriting is parallel, with two types of parallelism: (1) the total one, indicated by allP, which means that all nonterminal symbols from the array are rewritten, and (2) the maximal one, indicated by maxP, which means that a multiset of rules is applied which is maximal, no further rule can be added to it. For any two rules used simultaneously, no pixel of their left hand sides may overlap (i.e., cover the same pixel of the rewritten array). An important point appears here in what concerns the target indications of the rules: in each compartment, in a step we apply a multiset of rules with the same target indication. This is a very strong restriction, because it refers to all arrays from the compartment. In this paper, we work under this restriction. A weaker and somewhat more natural condition, which remains to be investigated (e.g., are the results proved below valid also in this case?), is to impose the restriction to use rules with the same target separately for each rewritten array (thus, separate arrays may be rewritten by rules with different targets). Of course, the two variants coincide for systems with only one axiom in the initial configuration. The arrays obtained by an allP or a maxP rewriting are placed in the region indicated by the target associated with the used rules, in the usual way in membrane computing. It is important to stress the fact that all arrays from a given compartment travel together during a computation. A computation is successful only if it halts; that is, it reaches a configuration where no rule can be applied to the existing arrays. The result of a halting computation consists of the arrays composed only of symbols from Tplaced in the region with label ioin the halting configuration. The set of all such arrays computed (we also say generated) by a system Πis denoted by A(Π). Note that a computation which produces a terminal array (hence no rule can be applied to it), but still can rewrite another array, is not halting; if the rewriting of one array continues forever, no matter how many terminal arrays were produced, then no result is obtained. We denote by PAPm(axk, α, β) the family of all array languages A(Π) generated by systems Πas above, with at most mmembranes, at most kinitial arrays in its compartments (Σm i=1card(Fi)≤k), with rules of type α∈ {REG, CF }, working in the β∈ {allP, maxP}mode. When mor kis not bounded, then it is replaced with ∗. On Parallel Array P Systems 297 The following results were proved in [6] (pri indicates the use of a priority relation on the rules): Lemma 1 (Lemma 3 in [6]). 2RLG ⊆PAP3(ax1, CF, allP ). Lemma 2 (Lemma 4 in [6]). P AP3(ax1, CF, allP )−2RLG =∅. Lemma 3 (Theorem 3 in [6]). LR∈P AP2(ax1, REG, allP, pri). Lemma 4 (Theorem 4 in [6]). LS∈P AP3(ax1, REG, allP, pri). In what follows, we will improve all these results in terms of the number of membranes in the first two lemmas and avoiding the priority relation in the last two lemmas (these two results are obtained at the price of using more than one axioms or using the maxP way of applying the rules). 4 Results The first two lemmas above can be easily improved. Proposition 1. 2RLG ⊆PAP2(ax1, CF, β), β ∈ {allP, maxP}. Proof. Let G= (Vh, Vv, Vi, T, S, Th, Rv) be a two-dimensional right-linear grammar. We construct the array P system Πindicated in Figure 2. The horizontal derivation is done in membrane 2. When the horizontal phase is completed, the array is moved to the skin membrane, where the vertical phase is performed. After the use of terminal rules, the array is moved back into the inner membrane. If it is not terminal, then the computation continues forever, by means of the rules A→A, A ∈Vi. These rules are also introduced in order to make the maxP computations to be allP computations. The equality L(G) = A(Π) is clear. ⊓⊔ Proposition 2. PAP2(ax1, CF, β)−2RLG =∅, β ∈ {allP, maxP }. Proof. Let us consider the array P system from Figure 3. From the axiom AB, we generate a string XnYn(Agoes to the left, simultaneously with Bgoing to the right), then, like in a two-dimensional right-linear grammar, in the skin region we go vertically, marking the pixels with ain the columns of Xand with bin the columns of Y. We obtain (moved in the central membrane) a rectangle with the same number of columns marked with aand with b, which is not in the family 2RLG (the same example was used also in [6]). The system works identically in the allP and maxP modes. ⊓⊔ Removing the priority from the other two results from [6] can be done, but making use of the possibility of having two axioms in the initial configuration of the systems. One of them will generate the desired arrays, the other one will generate “twin” arrays, which control the computation of the former arrays. 298 L. Pan, Gh. Paun ' & $ % ' & $ % 1 2 S X#→AY , for X→AY ∈Rh A→A, for A∈Vi X→A(out), for X→A∈Rh A→A(out), for A∈Vi A #→a B, for A→aB ∈Rv A→a(in), for A→a∈Rv Fig. 2. The array P system from the proof of Proposition 1 ' & $ % ' & $ % 1 2 AB #A→AX B#→Y B X→X Y→Y A→X(out) B→Y(out) X #→ a X Y #→b Y X→a(in) Y→b(in) Fig. 3. The array P system from the proof of Proposition 2 Proposition 3. LR∈PAP2(ax2, REG, β), β ∈ {allP, maxP}. Proof. We consider the array P system from Figure 4. The axioms and the rules are written on two columns, in the left one those which lead to the desired arrays, in the right one those handling the “twin” (control) arrays. The rules are similar, with the right column ones dealing with primed nonterminal symbols. On Parallel Array P Systems 299 The axiom in the left column is placed in the skin region, the one in the right column is placed in the inner membrane. In the first step, we move the inner axiom to the skin membrane, while removing the subscript 0 from all symbols A, B, A′, B′. Now we start the generation of the hollow rectangles. The bottom horizontal line of the arrays is generated in the skin membrane, by moving Band B′to the right. At a given step, we switch to moving vertically, with the arrays moved to membrane 2. We go upwards, synchronously, then the arrays are again moved to the skin membrane, with Dand D′being the current nonterminals. Both Dand D′go to left and, at some moment, Dis replaced with a(hence the “left” array is terminal (but we do not know whether the rectangle is completed). Moved again in membrane 2, the left array remains idle, while the right one can be rewritten – and, because of the parallelism, this must be done – if (and only if) D′has a non-marked pixel in its left. This happens if and only if the terminal array is not a complete hollow rectangle. The symbol D′′ will go up indefinitely, hence the computation never halts. Thus, only the halting computations produce elements in the language LR.⊓⊔ A similar result can be obtained for the language of hollow squares. Proposition 4. LS∈PAP2(ax2, REG, β), β ∈ {allP, maxP}. Proof. We consider the array P system from Figure 5, again with the axioms and the rules written on two columns, with the same significance as above. In the first step, we move the axiom from the skin region to the inner membrane, while also removing the subscript 0. In the inner membrane we start constructing the squarea, from the left bottom corner, growing here the left and the bottom edges. At some moment, the two arrays are moved to the skin membrane, where the upper and the right edges are constructed. The work on the “left” array is terminated at the moment when the arrays are moved to the inner membrane. We check here whether or not the square is completed. It is not completed if and only if the nonterminal B′′ has a non-marked pixel above it. If this is the case, the computation will continue forever, with B′′′ going to the right, hence the computation never halts. Checking all details remains as an exercise for the reader. ⊓⊔ The maxP mode of using the rules is, intuitively speaking, able of “appearance checking”, which is known to be a powerful feature of regulated grammars. This is confirmed also in our framework: we can generate the languages LR, LSby means of array P systems with only one axiom, at the price of using context-free rules – actually, in the construction below we have only three non-regular rules, of rather simple forms – used in the maxP mode. Proposition 5. LR∈PAP2(ax1, CF, maxP). Proof. We consider the array P system from Figure 6. We start in the skin membrane, growing the bottom edge. At some moment, we pass to growing the vertical edges, and the array is moved to the inner membrane. 300 L. Pan, Gh. Paun ' & $ % ' & $ % 1 2 A0aB0 A0→A B0→B A′ 0aB′ 0 A→A B#→aB # A→A a(in) # B→B a(in) #D→Da D→a(in) A′→A′ B′#→aB′ # A′→A′ a(in) # B′→B′ a(in) #D′→D′a D′→D′(in) # A→A a # B→B a A→a(out) B→D(out) # A′→A′ a # B′→B′ a A′→a(out) B′→D′(out) #D′→D′′ a # D′′ →D′′ a A′ 0→A′(out) B′ 0→B′(out) Fig. 4. The array P system from the proof of Proposition 3 After the array is moved to the inner membrane, the symbol Bintroduces two nonterminals, Xand B′. The latter one will grow the right hand edge, the symbol Xwaits unchanged until the array is moved back to the skin membrane. Here we both grow the upper edge, by means of the nonterminal C, and we change Xto Y, which is moved to the left, simultaneously with the symbol C. At any moment, Cis replaced with Dand Ywith Y′and the array is sent to membrane 2. Here we check whether the rectangle is completed. Dis replaced with a. The symbol Y′can be rewritten if and only if it has a non-marked pixel On Parallel Array P Systems 301 ' & $ % ' & $ % 1 2 A0 a B0 A0→A B0→B # A→A a B#→aB A→a(out) B→B(out) # A′→A′ a B′#→aB′ A′→A′(out) B′→B′(out) # B′′ →B′′′ a B′′′ #→aB′′′ A#→aA # B→B a A#→a¯ A B→¯ B ¯ A→a(in) ¯ B→a(in) A′ 0 a B′ 0 A′ 0→A′(in) B′ 0→B′(in) A′#→aA′ # B′→B′ a A′#→aA′′ B′→B′′ A′′ →a(in) B′′ →B′′ (in) Fig. 5. The array P system from the proof of Proposition 4 in its left hand place. If this is the case, hence the rectangle is not complete, the symbol Zis introduced; if not, the rule #Y′→Z#(out) cannot be applied (the maxP mode of using the rules allows rewriting only some nonterminals). Anyway, the array is moved back to the skin region (at least the rule D→a(out) is used). If Y′is still present, then it is simply erased by the rule Y′→#. Symbol Zcannot be removed, hence the computation leads to a terminal array if and only if the rectangle is completed. ⊓⊔ It remains as an exercise for the reader to use the same idea in order to prove that LS∈PAP2(ax1, CF, maxP}. On the other hand, we see no way to replace maxP with allP in these two results: LR∈PAP2(ax1, CF, maxP) and LS∈ PAP2(ax1, CF, maxP).