P and dP Automata: A Survey

P and dP Automata: A Survey Gheorghe P˘aun1,2and 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] Abstract. This is a quick survey of basic notions and results related to P automata (P systems with symport/antiport rules working in the accepting mode), with some emphasis on the recently introduced dP automata (a distributed version of the standard P automata), ending with some open problems and research topics which we find of interest in this area. 1 Introduction Membrane computing is a branch of natural computing aiming to abstract computing models from the structure and the functioning of the biological cell; the basic model of this research area (usually called a Psystem) consists of a hierarchical arrangement of membranes which delimit compartments where multisets of objects evolve according to given rules inspired by biology. Some rules are mimicking the biochemical reactions, other rules correspond to processes specific to cells, such as the selective passage of chemicals across membranes, in the form of symport and antiport operations (couples of molecules pass together, in the same direction in the case of symport and in opposite directions in the case of antiport, through specific protein channels). This is the framework where the present paper is placed: cell-like models, with the multisets of objects processed by communication only (moving them across membranes), using symport and antiport rules. Such systems were initially used in the generative manner (one starts from an initial configuration and one proceeds by a maximally parallel use of rules until reaching a halting configuration, one where no rule can be applied; the contents of a designated membrane in the halting configuration is considered as the result of the computation). Many variations of this basic model can be found in the membrane computing literature. We mention only the much investigated classes of tissue-like P systems and of spiking neural P systems. The reader is refereed to [15], [17], and to the domain website [21] for details. The idea of using a P system in the accepting mode has appeared already “from the old times”: start a computation by introducing a multiset in a specified membrane and, if (and only if) the computation halts, then this multiset is accepted. In the systems using only communication rules, such as those based on symport/antiport rules, a string can also be accepted in a natural way: just arrange in a sequence the objects (described by symbols) taken from the environment by the system during a halting computation. This idea was followed first in [6] (the paper was presented during the Workshop on Membrane Computing, Curtea de Arge¸s, 2002) and, almost concomitantly, in [10]. The devices introduced in the first paper are called P automata.Theyare usual P systems with symport/antiport rules supplemented with certain features: a set of accepting configurations (called “states” in [6]) is given and a mapping which associates a string with a multiset. The computation proceeds as usual in a P system with symport/antiport rules and it is considered successful only if it halts in an accepting state. In each step, the system takes some objects from the environment, hence a sequence of multisets can be associated with a successful computation. This sequence is “translated” into a string by the mapping mentioned above. Several papers were devoted to these devices (in particular, characterizations of regular, context-free, and recursively enumerable languages were obtained, and complexity investigations were carried out); we refer to [5] for details, including references. A simplified version of P automata was considered in [10]: successful computations are defined by halting only, and the mapping which passes from multisets (of objects introduced in the system) to strings is very simple – either all symbols are introduced in the accepted string (if several symbols are taken in the same step, then any permutation of them is introduced in the string, hence a set of strings can be associated with one computation), or only the objects from a given set, which is like in Chomsky grammars and Lindenmayer systems, where terminal and non-terminal symbols are considered and the strings in a language consists of only terminals. From now on we will work only with P automata in the sense of [10]. We call extended the automata which consider terminal symbols (hence they discard the non-terminal ones). We will give precise definitions in the next section. Note that any P system is a distributed parallel device, with several compartments/membranes working simultaneously, but the input (in the case of P automata) is taken from the environment only by the skin region. Looking for a computing model which can take parts of a global input and introduce them as “local” inputs in different components and then process these inputs separately in order to answer a “global question”, so-called dP systems were recently introduced in [16]. In the general case, such systems consist of a given number of components in the form of a usual P system, of any type, which can have their separate inputs and communicate from skin to skin membranes by means of antiport rules like in tissue-like P systems. In this framework, communication complexity issues can be investigated, as in [12]. (Some previous proposals towards a communication complexity of P systems were made in [1], but mainly related to the communication effort in terms of symport/antiport rules in a usual P system, not an explicitly distributed one.) The case of P automata was considered in some details – and this leads to the notion of dP automata.The possibility of accepting languages of various types in Chomsky hierarchy in a distributed way, using a bounded number of communication rules and also with some (linear) speed-up was proven. The study of dP automata was continued in [9], by comparing their power with that of usual P automata and with families of languages in the Chomsky hierarchy. As expected, due to the distribution (and synchronization), dP automata are strictly more powerful than P automata. Also expected is the fact that each regular languages can be recognized by a P automaton. In the present note, we recall the results from [16] and [9]. A theorem from [9] gives a representation of recursively enumerable (RE) languages starting from languages recognized by dP automata, similar to the representation of RE languages in terms of context-sensitive languages; it is not shown in [9] whether this new representation is non-trivial, in the sense that the relation between the family of languages recognized by dP automata and the family of contextsensitive languages is not settled (the inclusion is obvious, but it is not shown to be proper). We clarify here this point, by finding a context-sensitive language which cannot be accepted by a dP automaton. Along the paper as well as in the end of it, we formulate a series of open problems and research topics (especially about dP automata) which we find of interest. 2dPAutomata We directly introduce the dP automata, by whose particularization we get the notion of a P automaton. The reader is assumed to be familiar with basics of membrane computing, e.g., from [15], [17], and of formal language theory, e.g., from [19], [20]. 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, contextfree, context-sensitive, and recursively enumerable languages, respectively. 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,w i,1,...,w i,ki,E,R i,1,...,R i,ki) is a symport/antiport P system of degree ki(Ois the alphabet of objects, μiis a membrane structure of degree ki,wi,1,...,w i,kiare the multisets of objects present in the membranes of μiin the beginning of the computation, Eis the alphabet of objects present – in arbitrarily many copies – in the environment, and Ri,1,...,R i,ki are 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∗,andthe antiport rules are of the form (u, out;v,in), where u, v ∈O∗;notethatwe 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,s j), where 1 ≤i, j ≤n, i =j, and u, v ∈O∗,uv =λ. The systems Π1,...,Π nare called components of Δand the rules in Rare called communication rules.Forarule(si,u/v,s j), |uv|is the weight of this rule. Each component can take an input, work on it, and communicate with other components. The communication is done by means of rules in R, but, because the environment is common, the components can also communicate, in two steps, through the environment. In the constructions involved in the proofs of the results recalled below this latter possibility is systematically avoided, but from a formal point of view this raises already a research topic: Is any difference between the power and/or the efficiency of dP systems whose components are allowed and those whose components are not allowed to communicate through the environment? How this communication can be avoided? (Some suggestions are given in [16], e.g., to consider a “local environment” for each component, not accessible to other components.) A halting computation with respect to Δaccepts the string x=x1x2...x n over Oif the components Π1,...,Π n, starting from their initial configurations, using the symport/antiport rules as well as the inter-components communication rules, in the non-deterministic maximally parallel way, bring from the environment the substrings x1,...,x n, respectively, and eventually halts. 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. Three communication complexity measures were defined in [16], following [1], counting the number of communication steps (parameter ComN), of communication rules (ComR), or the total weight of communication rules (ComW)used during a computation. Based on these measures, the notions of weak parallelizability and of efficient parallelizability are introduced. For instance, a language L⊆V∗is said to be (n, m)-weakly ComX parallelizable,forsomen≥2,m≥1, and X∈{N,R,W}, if there is a dP automaton Δwith ncomponents and there is a finite subset FΔof Lsuch that each string x∈L−FΔcanbewrittenas x=x1x2...x n,with||xi|−|xj|| ≤ 1 for all 1 ≤i, j ≤n, each component Πiof Δtakes as input the string xi,1≤i≤n, and the string xis accepted by Δby a halting computation δsuch that ComX(δ)≤m. A language Lis said to be weakly ComX parallelizable if it is (n, m)-weakly ComX parallelizable for some n≥2,m≥1. Note that (i) the string is distributed in equal parts, modulo one symbol, to the components of the dP automaton (like in communication complexity area, [12]; one says that the string is distributed in a balanced way) and (ii) the communication complexity, in the sense of measure ComX, is bounded by the constant m. It is said nothing about the length of the computation, that is why a stronger version of parallelizability is introduced, the efficient one. In what follows, we allow the dP system to perform communications of an arbitrary complexity, while the length of the computation is not taken into consideration, hence we ignore these aspects. Specifically, for a dP automaton Δof degree nwe define the language L(Δ), of all strings x∈O∗such that we can write x=x1x2...x n,with||xi|−|xj|| ≤ 1for all 1 ≤i, j ≤n, each component Πiof Δtakes as input the string xi,1≤i≤n, and the computation halts. Note again that, like in the communication complexity area, the string is distributed in equal parts, modulo one symbol, to the components of the dP automaton. This acts like a strong restriction for our devices. If this condition is not imposed, hence any decomposition of the string xcan be considered, then a superlanguage of L(Δ) is obtained. Like in [16], [9], in what follows we only consider the balanced distribution case; the study of the unbalanced case remains a topic for future research (we will mention this question again in the last section). We denote by LdPnthe family of languages L(Δ), for Δof degree at most n. A dP automaton of degree 1 is a usual P automaton – of a non-extended type: all symbols are introduced in the accepted string. If a terminal set of objects is considered, then we obtain an extended P automaton (formally, we have a device Π=(O,T, μ, w1,...,w m,E,R 1,...,R m), with T⊆O, working as a usual P automaton and considering only the symbols from Tin the accepted strings and ignoring those from O−T). We denote by LP the family of languages recognized by non-extended P automata (hence LP =LdP1)andbyELP the family of languages recognized by extended P automata. (Note that we ignore the weight of symport and antiport rules, but these parameters, usual when investigating symport/antiport P systems, can be considered also here.) If the subscript nin LdPnis arbitrary, then we replace it by ∗. A terminal alphabet can be considered also for dP automata, but this is not of much interest: ELdP1=ELP, which is known to equals RE. 3 On the Power of P Automata Extended P automata were proved already in [10] to be computationally universal: Theorem 1. ELP =RE. Actually, rather simple P automata (e.g., with only one membrane), also working in the deterministic way, are shown to be able to simulate language accepting register machines. In turn, because in the non-extended case the number of objects present in the system is comparable with the number of objects taken from the environment (the initial multisets are fixed), hence with the length of the accepted string, we immediately have: Theorem 2. LP ⊆CS. However, we know no other result about non-extended P automata reported before the introduction of dP automata, which is somehow strange, because the power of non-extended P automata raise interesting (and intuitively non-trivial) problems. Some of these problems were addressed in [9]; we will recall the respective results, after recalling an example, which can illustrate the way a P automaton works. The automaton (with six membranes) is given first formally and then in Figure 1, represented as usual in membrane computing (with the rules near the membranes with which they are associated). Π=(O, μ,w1,w 2,w 3,w 4,w 5,w 6,E,R 1,R 2,R 3,R 4,R 5,R 6), O={a, b, c, d, e, f, g, #}, μ=[[[ ] 3[] 4]2[] 5[] 6]1, w1=c, w2=de, w3=λ, w4=#, w5=fgg, w6=#, E={a, b, c, d}, R1={(c, out;aa, in),(a, out;c, in),(d, out;bb, in),(b, out;d, in)}, R2={(e, out),(ae, in),(d, out;fe,in),(be, in),(g,in),(#,in),(#,out)}, R3={(gab,in),(g,out)}, R4={(#,out;ga,in),(#,out;gb,in)}, R5={(f,out;c, in),(gg,out;d, in)}, R6={(#,out;e, in),(eg, in)}. This automaton recognizes the non-regular language L(Π)={(a2c)s(b2d)s|s≥ 1}–wedenoteitbyL1, for a later reference. We start by bringing the object eout of membrane 2, at the same time with introducing two copies of afrom the environment. If ewill enter membrane 6, then the computation never halts, hence the object eshould be “kept busy” by means of a copy of object a, which brings eback to membrane 2 (while the other copy of aexits, in exchange with one copy of object c). This process is repeated for a number of times and then, instead of going out, the object centers membrane 5, releasing from here the object f. Together with e, object fenters membrane 2, releasing d.Fromnowon,dplays the same role as cbefore and b ' & $ % ' & $ % ' & $ % ' & $ % ' & $ % ' & $ % 1 2 3 4 5 6 # fgg # c de (e, out) (ae, in) (d, out;fe,in) (be, in) (g,in) (#,in) (#,out) (gab,in) (g,out) (#,out;ga,in) (#,out;gb,in) (f,out;c, in) (gg,out;d, in) (#,out;e, in) (eg, in) (c, out;aa, in) (a, out;c, in) (d, out;bb, in) (b, out;d, in) Fig. 1. A P automaton recognizing the language L1 plays the role of a, hence we bring inside a string of the form (bbd)s,s≥1. After a while, also denters membrane 5, releasing the two copies of g. One is used for moving the object einside membrane 6 without releasing the trap object #, while the other copy of genters membrane 2, and start here checking whether the number of copies of aand bstored here are equal. If this is not the case, then gtogether with exceeding aor with an exceeding benters membrane 4, and the trap object # is brought to region 2, hence the computation never stops. Therefore, we have L1∈LP. The idea of the system in Figure 1 can be extended so that we can check the equality of three blocks of repeated symbols, hence also non-context-free languages can be obtained. We summarize these remarks as: Theorem 3. LP contains linear non-regular, as well as non-context-free languages. Thus, the non-extended P automata can recognize “complex” languages – but they fail to recognize other “simple” languages. Here are two necessary conditions for a language to be in LP proved in [9]. We start with an easy result, refuting however many languages. Lemma 1. For every language L⊆V∗,L ∈LP, which is not regular there is a string w∈Lwhich can be written in the form w=w1abw2,forsome w1,w 2∈V∗and a, b ∈V(not necessarily distinct) such that w1baw2∈L. This lemma implies, for instance, that the linear language L2={(ab)n(ac)n|n≥1} is not in LP. Actually, a more general consequence of Lemma 1 is drawn in [9]: Theorem 4. All families of languages which include strictly the family of regular languages and are closed under λ-free morphisms contain languages which are not in LP. We pass now to the second necessary condition for a language to be in LP. Lemma 2. Let Vbe an alphabet with at least two elements and f:V∗−→ V∗ an injective mapping. The language Lf={wf(w)|w∈V∗}is not in the family LP. The proof is based on the observation that the number of configurations of a P automaton which has brought inside msymbols is bounded by a polynomial in m, but there are more than 2mdifferent strings of length mover an alphabet with more than two symbols (hence exponentially many), which makes impossible the matching between the two halves of the strings. We will extend this proof idea to dP automata in the next section. As a consequence of the previous lemma, for instance, the context-sensitive language, L3={wf(w)|w∈{a, b}∗}for f(a)=a,f(b)=b,isnotinLP. Pleasantly enough (and somewhat expected), P automata can recognize all regular languages: Theorem 5. REG ⊂LP. 4 On the Power of dP Automata Let us first note that the language L2is in LdP2and the same is true for L3; this language is recognized by the dP automaton (of degree 2, with arbitrarily many communications) indicated in Figure 2, hence we have Theorem 6. LdPn−LP =∅for all n≥2. The following theorem is classic in formal language theory – see, e.g., [20]: Theorem 7. For every language L∈RE, L ⊆V∗, there is a language L∈CS and two symbols a, c /∈Vsuch that: (i) L⊆L{c}a∗, (ii) for each w∈Lthere is i≥0such that wcai∈L. ' & $ % ' & $ % s1 c s2 (s1,a/λ,s 2) (s1,b/λ,s 2) (s1,λ/a ,s 2) (s1,λ/b ,s 2) (a, out;a,in) (b, out;b,in) (c, out;a, in) (c, out;b, in) (a,out;a, in) (a,out;b, in) (b,out;a, in) (b,out;b, in) (a,out) (b,out) Fig. 2. A dP automaton accepting the language L3 Otherwise stated, the two languages are “the same” up to a tail of arbitrary length added to strings in L. Because the initial configuration of a dP automaton is given and the objects brought into the system from the environment are part of the recognized string, the workspace of the automaton is linearly bounded with respect to the string, hence Theorem 2 can be extended to: Theorem 8. LdP∗⊆CS. In [9] it is conjectured that the above inclusion is proper. We confirm here this hypothesis: Lemma 3. The language L4={(ww)s|w∈{a, b}+,s ≥2},wherewis obtained from wby priming the symbols a and b, is not in the family LdP∗. Proof. Assume that L4=L(Δ) for some dP automaton Δwith ncomponents, Π1,...,Π n,n≥2. Consider the sublanguage Hnof L4consisting of strings with nblocks ww, i.e., Hn={(ww)n|w∈{a, b}+}⊂L4. Because of the balanced distribution of inputs to the ncomponents of Δ,eachΠi has to take from the environment a string ww. Consider the strings wof length m, for some arbitrarily large m, and examine the state of the dP automaton in the moment when component Π1has “read” from the environment the symbols of w. (There is a step when exactly the symbols of wwere introduced in Π1:the next symbol is primed and, if it enters the system at the same time with a symbol