dP Automata versus Right-Linear Simple Matrix Grammars

dP Automata versus Right-Linear Simple Matrix Grammars Gheorghe P˘aun1,2, Mario J. P´erez-Jim´enez2 1Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania 2Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Summary. We consider dP automata with the input string distributed in an arbitrary (hence not necessary balanced) way, and we investigate their language accepting power, both in the case when a bound there is on the number of objects present inside the system and in the general case. The relation with right-linear simple matrix grammars is useful in this respect. Some research topics and open problems are also formulated. 1 Introduction dP automata are a class of computing devices considered in membrane computing area in order to have a distributed language accepting machinery, with the strings to recognize being split among the components of the system and with these components working in parallel on the input strings. In the general case, dP systems consist of a given number of components in the form of a usual symport/antiport P system, which can have their separate inputs and communicate from skin to skin membranes by means of antiport rules like in tissue-like P systems. Such devices were introduced in [7] and further investigated in [3], [8], [9], mainly comparing their power with that of usual P automata and with families of languages in the Chomsky hierarchy. In the basic definition and in all these papers, following the style of the communication complexity area (see, [4]), the so-called balanced mode of introducing the input string is considered: the string is split in equal parts, modulo one symbol, and distributed among components. Here we consider the general case, with no restriction on the input string distribution; each component just takes symbols from the environment when it can do it it, without any restriction on their number. This is a very natural and general set-up, which, however, was only incidentally investigated so far. Two cases are distinguished: with a bound on the size of the system (on the total number of objects present inside) and without such a bound. Both cases are naturally related to 294 Gh. P˘aun, M.J. P´erez-Jim´enez a classic family of regulated grammars, the simple matrix grammars of [5] (see also [2]). Actually, as expected, right-linear simple matrix grammars are closely related to dP automata, and we will examine below this connection (looking for mutual simulations among the two types of language identifying machineries). This connection was already pointed out in [8], where the conjecture was formulated that, in the same way as a usual finite automaton can be simulated by a P automaton, a right-linear simple matrix grammar can be simulated by a dP automaton. We confirm here this conjecture (in the general, not the balanced case). 2 Formal Language Theory Prerequisites The reader is assumed to have some familiarity with basics of membrane computing, e.g., from [6], [10], and of formal language theory, e.g., from [2], [11], but we recall below all notions necessary in the subsequent sections. In what follows, V∗is the free monoid generated by the alphabet V,λis the empty word, V+=V∗− {λ}, and |x|denotes the length of the string x∈ V∗.REG, LIN, CF, CS, RE denote the families of regular, linear, context-free, context-sensitive, and recursively enumerable languages, respectively. Essential below will be the right-linear simple matrix grammars introduced in [5]. Such a grammar of degree n≥1 is a construct of the form G= (N1, . . . , Nn, T, S, M), where N1, N2, . . . , Nn, T are pairwise disjoint alphabets (we denote by Nthe union of N1, . . . , Nn), S /∈T∪N, and Mcontains matrices of the following forms: (i) (S→x), x ∈T∗, (ii) (S→A1A2. . . An), Ai∈Ni,1≤i≤n, (iii) (A1→x1B1, . . . , An→xnBn), Ai, Bi∈Ni, xi∈T∗,1≤i≤n, (iv) (A1→x1, . . . , An→xn), Ai∈Ni, xi∈T∗,1≤i≤n. A derivation starting with a matrix of type (ii) continues with an arbitrary numbers of steps which use matrices of type (iii) and ends by applying a matrix of type (iv). We denote by L(G) the language generated in this way by Gand by RSMn the family of languages L(G) for right-linear simple matrix grammars Gof degree at most n, for n≥1. The union of all these families is denoted by RSM∗. The strict inclusions RSMn⊂RSMn+1, n ≥1, are known. Moreover, REG =RSM1, RSM∗⊂CS,RSM∗is incomparable with LIN and CF, all languages in RSM∗ are semilinear, and this family is closed under union, intersection with regular languages, direct and inverse morphisms (but not under intersection, complement and Kleene +). Clearly, a normal form can be easily found for these grammars: in matrices of type (iii) we can ask to have xi∈T∪ {λ},1≤i≤n, and in matrices of type (iv) we can have xi=λfor all 1 ≤i≤n. dP Automata versus Right-Linear Simple Matrix Grammars 295 3 dP Automata We introduce now the computing devices we investigate in this paper, also giving a relevant example. As usual in membrane computing, the multisets over an alphabet Vare represented by strings in V∗; a string and all its permutations correspond to the same multiset, with the number of occurrences of a symbol in a string representing the multiplicity of that object in the multiset. (We work here only with multisets of finite multiplicity.) The terms “symbol” and “object” are used interchangeably, all objects are here represented by symbols. AdP automaton (of degree n≥1) is a construct ∆= (O, E, Π1, . . . , Πn, R), where: (1) Ois an alphabet (of objects); (2) E⊆O(the objects available in arbitrarily many copies in the environment); (3) Πi= (O, µi, wi,1, . . . , wi,ki, E, Ri,1, . . . , Ri,ki) is a symport/antiport P system of degree ki(Ois the alphabet of objects, µiis a membrane structure of degree ki,wi,1, . . . , wi,kiare the multisets of objects present in the membranes of µi in the beginning of the computation, Eis the alphabet of objects present – in arbitrarily many copies – in the environment, and Ri,1, . . . , Ri,kiare finite sets of symport/antiport rules associated with the membranes of µi; the symport rules are of the form (u, in),(u, out), where u∈O∗, and the antiport rules are of the form (u, out;v, in), where u, v ∈O∗; note that we do not have an output membrane), with the skin membrane labeled with (i, 1) = si, for all i= 1,2, . . . , n; (4) Ris a finite set of rules of the form (si, u/v, sj), where 1 ≤i, j ≤n, i 6=j, and u, v ∈O∗, uv 6=λ. The systems Π1, . . . , Πnare called components of ∆and the rules in Rare called communication rules. For a rule (si, u/v, sj), |uv|is the weight of this rule. Using a rule (u, in),(u, out) associated with a membrane imeans to bring in the membrane, respectively to send out of it the multiset u; using a rule (u, out;v, in) associated with a membrane imeans to send out of the membrane the objects of multiset uand, simultaneously, to bring in the membrane, from the region surrounding membrane i, the objects of multiset v. A communication rule (si, u/v, sj) moves the objects of ufrom component Πito component Πj, simultaneously with moving the objects in the multiset vin the opposite direction. Each component Πican take symbols from the environment, work on them by using the rules in sets Ri,1, . . . , Ri,ki, and communicate with other components by means of rules in R. A halting computation with respect to ∆accepts the string x=x1x2. . . xn over Oif the components Π1, . . . , Πn, starting from their initial configurations, using the symport/antiport rules as well as the inter-components communication 296 Gh. P˘aun, M.J. P´erez-Jim´enez rules, in the non-deterministic maximally parallel way, bring from the environment the substrings x1, . . . , xn, respectively, and eventually halts. A problem appears in the case when several objects are read at the same time from the environment, by several rules or by a single rule of the form (u, out;v, in), with |v| ≥ 2; in such a case any permutation of the symbols brought in the system in the same step are considered as a valid substring of the input string (thus, a computation can recognize several strings, differing to each other by permutations of certain substrings). Note that we impose here no condition on the relative lengths of strings x1, x2, . . . , xn(as it is done in previous papers dealing with dP automata, under the influence of communication complexity area). We denote by L(∆) the language of all strings recognized by ∆in this way, and by LdPnthe family of languages L(∆), for ∆of degree at most n≥1. The union of all these families is denoted by LdP∗. The dP automata are synchronized devices, a universal clock exists for all components, marking the time in the same way for the whole dP automaton. When the system has only one component, then we obtain the usual notion of a P automaton, as investigated in a series of papers (mainly in the extended version, with a terminal alphabet of objects – see the respective chapter in [10] and the references therein). We denote by LP the family of languages recognized by P automata. Hence, LP =LdP1and, from [3], it is known that REG ⊂LP ⊂CS and LP is incomparable with CF. We consider now a somewhat surprising example, of a dP automaton of degree 2, generating a complex language, L1={ww |w∈ {a, b}∗}. The automaton is given in Figure 1, in the standard way of representing a dP automaton. We have O={a, b, c1, c2, d, #}and E={a, b}. All antiport rules which bring objects from the environment are of weight one, hence the number of objects present in the system is constant, four in each component. In the first step, objects drelease c2ain the skin region of the first component and c1ain the second. Each symbol acan bring either an aor a bfrom the environment and, at the same time, the objects c1, c1are interchanged between the two components (otherwise, they release the trap object #, which will oscillate forever across membranes (1,1), respectively, (2,1), and the computation never stops). With c1α, α ∈ {a, b}, in the first component and c2β, β ∈ {a, b}, in the second one, the only continuation which does not release the trap object is possible when α=β, by using the communication rule (s1, c1α/c2α, s2) (if one of the symbols α, β brings new symbols from the environment, the corresponding c1, c2 should enter the membrane (1,2) or (2,2), bringing out the object #). We obtain a configuration as that we started with, hence the process can be iterated. If, at any moment when c2is in Π1and c1is in Π2, one of the rules (c2α, in), α ∈ {a, b}, is used in the first component, or (c1α, in), α ∈ {a, b}, is used in the second component, then this should be done simultaneously in both components, otherwise again one of c1, c2has to release the trap object. In conclusion, the strings read from the environment by the two components are identical, hence L(∆) = L1. dP Automata versus Right-Linear Simple Matrix Grammars 297 ' & $ % ' & $ % º ¹ · ¸ º ¹ · ¸º ¹ · ¸ º ¹ · ¸ -¾ s1 d (1,1) a c2 (c2a, out;d, in) (c2a, in) (c2b, in) (#, in) (#, out) # (#, out;c1, in) (#, out;c2, in) (a, out;a, in) (a, out;b, in) (b, out;a, in) (b, out;b, in) (s1, c1a/c2a, s2) (s1, c1b/c2b, s2) (s1, c2/c1, s2) s2 d (2,1) c1 a (c1a, out;d, in) (c1a, in) (c1b, in) (#, in) (#, out) (2,2)(1,2) # (#, out;c2, in) (#, out;c1, in) (a, out;a, in) (a, out;b, in) (b, out;a, in) (b, out;b, in) Fig. 1. A dP automaton recognizing the language L1. Note the important facts that the system reads the input in a balanced way and that it is bounded, the total number of objects present inside is always bounded by a constant (8 in our case) given in advance. This last characteristics is important, so that we denote by LdPb n, n ≥1,the family of languages recognized by bounded dP automata of degree at most n; when nis not specified, we replace it by ∗. 4 The Power of dP Automata We start by reformulating in a more general way a result already suggested by a proof in [9]. Theorem 1. LdPb n⊆RSMn, for all n≥1. Proof. Let ∆be a dP automaton of degree n(with the set of objects O) which is bounded. Then, the set of all its configurations is finite. Let σ0, σ1, . . . , σpbe this set, with σ0being the initial configuration. We construct the following right-linear simple matrix grammar: 298 Gh. P˘aun, M.J. P´erez-Jim´enez G= (N1, . . . , Nn, O, S, M),with Ni={(σj)i|0≤j≤p}, i = 1,2, . . . , n, M={(S→(σ0)1(σ0)2. . . (σ0)n)} ∪ {(σi)1→α1(σj)1, . . . , (σi)n→αn(σj)n)| from configuration σithe dP automaton ∆can pass to the configuration σjby a correct transition, taking from the environment the objects α1, . . . , αnby its components, where αs∈O∪ {λ},1≤s≤n} ∪ {(σh)1→λ, . . . , (σh)n→λ)|σhis a halting configuration}. Note that all nonterminals in the rules of a matrix contain the same “core information”, namely the current configuration of the system, hence the complete control of the system working is obtained in this way. The equality L(∆) = L(G) is obvious. 2 This result cannot be extended to arbitrary dP automata. Actually, we have: Theorem 2. LdP2−RSM∗6=∅. Proof. Let us consider the following dP automaton: ∆= (O, E, Π1, Π2, R),with O={a, c, d, e, f, #}, E={a, c, d, e}, Π1= (O, [ ]s1, f, E, {(f, out;a, in),(a, out;aa, in)}), Π2= (O, [ [ ](2,1) ]s2, E, {(f, out;d, in),(a, out;c, in),(d, out;e, in)}, {(f, out;f, in)}), R={(s1, a/λ, s2)}. For an easier examination of the work of the system, we also represent it graphically, in Figure 2. Let us look for strings accepted by this dP automaton which are of the form aidcje, for some i, j ≥1. After introducing the symbol ain the first component, let us assume that for n≥0 steps we use here the rule (a, out;aa, in), hence we produce 2ncopies of ain Π1, while the second component uses the rule (f, out;f, in)∈R(2,1). Suppose now that p≥0 copies of aremains in the first component and the others r= 2n−pare moved to the second component. Here, all rcopies of amust go out, in exchange of objects c, hence the string read by the second component starts with cr. At the same time or one step before, the second component must introduce the symbol d. This object becomes immediately e, hence the exchange of afor cshould be done either in the same step with reading dor at the same time with reading ein dP Automata versus Right-Linear Simple Matrix Grammars 299 ' & $ % ' & $ % ¾ ½» ¼ - s1 f (f, out;a, in) (a, out;aa, in) (s1, a/λ, s2) s2 f f (2,1) (f, out;f, in) (f, out;d, in) (d, out;e, in) (a, out;c, in) Fig. 2. A dP system recognizing a language not in RSM∗ the second component (because any permutation of the objects is allowed in the string, either variant is possible). However, after e, we do not want to have any symbol, hence all copies of awere already moved to the second component, and thus the work of the first component stops. When introducing the symbol din the second component, the pcopies of afrom the first component cannot use the rule (a, out;aa, in), but they must come immediately in the second component, to introduce chere at the same time with introducing e. Therefore, if the string has the form aidcje, then i=j= 2nfor some n≥0 (n= 0 is obtained if the unique aintroduced in the first step in Π1is immediately sent to component Π2). Consequently, L(∆)∩a∗dc∗e={a2ndc2ne|n≥0}, which is not in RSM∗, hence also L(∆) is not in RSM∗: this family is closed under intersection with regular languages and contains only semilinear languages. 2 Note that the previous construction takes the input string in an almost balanced way, and, if in the first step, the first component uses a rule (f, out;dea, in) instead of (f, out;a, in), then we have a balanced functioning, hence the result in the previous theorem holds true also for the balanced way of defining the recognized string. We pass now to the counterpart of Theorem 1 announced above. Theorem 3. RSMn⊆LdPb n+1, for all n≥1. Proof. Let us consider a right-linear simple matrix grammar G= (N1, . . . , Nn, T, S, M) as introduced in Section 2, with the alphabets N1, N2, . . . , Nn(their union is denoted by N) and T. Matrices of the form (i), (S→x), x ∈T∗, can be replaced by matrices of forms (ii), (iii) and (iv), in an obvious way, hence we assume that we do not have such matrices. We assume all matrices labeled in a one-to-one way; let mj: (A1→x1B1, . . . , An→xnBn), with 1≤j≤k, be all matrices of type (iii), with Ai, Bi∈Ni, xi∈T∗,1≤i≤n. Similarly, let mj: (A1→x1, . . . , An→xn), with k+ 1 ≤j≤p, be all matrices of 300 Gh. P˘aun, M.J. P´erez-Jim´enez type (iv), with Ai∈Ni, xi∈T∗,1≤i≤n. Without any loss of the generality we can assume that all strings xiin these matrices are from T∪ {λ}. For each matrix, of any form, mj: (A1→u1, . . . , Ai→ui, . . . , An→un), let us consider the symbol [mj, Ai→ui] (thus identifying the matrix and its ith rule), and let Xj(i) be a shorthand for it. Consider the alphabets Mi={Xj(i)|1≤j≤p},for all 1 ≤i≤n. We also denote by M0 ithe alphabet of primed symbols in Mi. For a matrix mj: (A1→x1B1, . . . , An→xnBn) of type (iii), let us denote lhsj=A1A2. . . Anand rhsj=B1B2. . . Bn. Similarly, for a matrix mj: (A1→ x1, . . . , An→xn) of type (iv), we denote lhsj=A1A2. . . An. If rhsj=lhsk, then we write mj;mk. Similarly, we write S;mjif (S→A1A2. . . An)∈Mand A1A2. . . An=lhsj. For a set Q, we denote by Qalso the multiset consisting of the elements of Q, with the multiplicity one for each of them (hence Qcan be considered also as the string composed by the elements of the set, in any ordering). We are now ready to construct the dP system we look for (a0is an arbitrary symbol of Tfixed in advance): ∆= (O, E, Π1, . . . , Πn+1, R),with : O= n [ i=1 (Mi∪M0 i)∪T∪ {ci|1≤i≤n}∪{d, f, #}, E=T, Πi= (O, [ [ ](i,1)[ ](i,2) ]si, λ, M0 iTci,#, Rsi, R(i,1), R(i,2)), Rsi={(a, out;b, in)|a, b ∈T}, R(i,1) ={(X0 j(i), out;Xj(i), in), (Xj(i)cia, out;X0 j(i)cia, in)|1≤j≤p, if Xj(i) = [mj, Ai→aBi], a ∈T} ∪ {(X0 j(i)a, out;Xj(i)a, in), (Xj(i)cia, out;X0 j(i)cia, in)|1≤j≤p, a ∈T, if Xj(i) = [mj, Ai→Bi]} ∪ {(#, in),(#, out)}, R(i,2) ={(#, out;ci, in)} ∪ {(#, out;Xj(i), in)|1≤j≤p, if Xj(i) = [mj, Ai→Bj]}, for all 1 ≤i≤n, Πn+1 = (O, [ [ ](n+1,1) ]sn+1 , c1. . . cnf, M2 1. . . M2 nTnan 0,∅, R(n+1,1)), R(n+1,1) ={(Xj(1) . . . Xj(n)an 0, out;f, in)|1≤j≤pif S;mj} ∪ {(Xk(1)a1. . . Xk(n)an, out;Xj(1)a1. . . Xj(n)an, in) |1≤j, k ≤p, ai∈T, 1≤i≤n, if mj;mk} dP Automata versus Right-Linear Simple Matrix Grammars 301 ∪ {(Xj(1)c1a1. . . Xj(n)cnan, in) |ai∈T, 1≤i≤n, if mjis a terminal matrix}, R={(si, λ/ci, sn+1), (si, ci/Xj(i)a, sn+1, (si, Xj(i)cia/λ, sn+1)|1≤j≤p, 1≤i≤n, a ∈T}. This dP system, with one component Πiand with Πn+1 given in full details, is represented in Figure 3. ' & $ % ' & $ % ' & $ % ' & $ % ' & $ %                       6 ? 6 ? 6 ? s1 (1,1) (1,2) ... si (i, 1) (i, 2) ... sn (n,1) (n,2) sn+1 (n+1,1) (a, out;b, in), a, b ∈T (X0 j(i), out;Xj(i), in), (Xj(i)cia, out;X0 j(i)cia, in), if Xj(i) = [mj, Ai→aBi], a ∈T, 1≤j≤p (X0 j(i)a, out;Xj(i)a, in), (Xj(i)cia, out;X0 j(i)cia, in), if Xj(i) = [mj, Ai→Bi],1≤j≤p, a ∈T (#, in) (#, out) (#, out, ci, in) (#, out;Xj(i), in), if rule iin mjis Ai→Bi,1≤j≤p (si, λ/ci, sn+1) (si, ci/Xj(i)a, sn+1), a ∈T, 1≤j≤p (si, Xj(i)cia/λ, sn+1), a ∈T, 1≤j≤p c1c2...cnf Sn i=1 M2 i Tn an 0 (Xj(1) ...Xj(n)an 0, out;f, in) if S;mj (Xk(1)a1...Xk(n)an, out;Xj(1)a1. . . Xj(n)an, in), if mj;mk (Xj(1)c1a1...Xj(n)cnan, in) if mjis terminal Fig. 3. The dP system in the proof of Theorem 3 The components Πi,1≤i≤n, simulate the corresponding “component” of the grammar G, while Πn+1 is a “synchronizer” of the other components, it takes no