A Note on Complexity Measures for Probabilistic P Systems

A Note on Complexity Measures for Probabilistic P Systems Andr´es Cord´on-Franco, Fernando Sancho-Caparrini (University of Sevilla, Spain {acordon, fsancho}@us.es) Abstract: In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves. Key Words: P systems, Entropy, Natural Computing Category: F.1.1, G.2.2, H.1.1 1 Introduction In [P˘aun 00] Gh. P˘aun introduced a new computing device, called P system, within the framework of Natural Computing based upon the observation that the processes which take place in the complex structure of a living cell can be considered as computations. Since then, these complex systems have been investigated from many points of view. For instance, they have been shown to be able to solve hard problems in lower time than classical devices. Starting from an initial state, they evolve by means of rules that can modify the objects inside the system and even the system own structure. If we look at P systems as probabilistic devices where several different computations can be reached from a given initial state, it is intuitively obvious that some uncertainty in the result provided by the P system arises. In order to define some quantitative property allowing us to measure this uncertainty, we begin with some general observations about the notion of a system. A common-sense definition for the notion of a system is a group of units so combined as to form a whole and to operate in unison. There are several other definitions in the literature. For example, a technical definition was presented by Hall and Fagan [Hall and Fagan 80]: A system is a set of objects together with relationships between the objects. Formalists present a very simple and general definition: given a family of base sets X1,...,X n, a system Sis any relation (subset) in X=Πn i=1Xi. Constructivists disagree with this formalist point of view, emphasizing that the natural world of evolving systems can never be captured by formal systems with an apriorifixed and finite amount of base sets; hence, Journal of Universal Computer Science, vol. 10, no. 5 (2004), 559-566 submitted: 1/4/04, accepted: 10/4/04, appeared: 28/5/04 © J.UCS they propose open systems which define their elements and base sets during the processes of their evolution. Nevertheless, there are some common characteristics in all approaches above: –A variety of distinct entities. –These entities are involved in some kind of relations. –These relations are sufficient to generate a new entity, of a higher complexity. In the last 20 years, the study of complex systems has emerged as a recognized field in its own right, although a good definition of what a complex system is has eluded rigorous formulation. Attempts to formalize the concept of complexity go back even further, to Shannon’s Information Theory [Shannon 48], where the concepts of entropy and information of a system (as measures of uncertainty and variety) were defined. 2 Entropy and Information The state space,S, of a system is the set of all possible states that the system can be in. An essential component in the study of a system is a quantitative measure for the size of its state space. This measure is usually called variety and it represents the freedom of the system to reach a particular state, and thus the uncertainty we have about which state the system is in. The variety, V,is defined as the number of elements in the state space or, more commonly, as V=log 2(|S|), if we encode the states of the system by bits. A variety of one bit, V= 1, means that the system has two possible states, that is, one choice. In the case of nbinary variables, V=log 2(2n)=nis therefore equal to the number of independent choices. Thus, the system variety, V, measures the number of possible states the system can exhibit, and corresponds to the number of independent binary variables. But, in general, the variables used to describe a system are neither binary nor independent. If the actual variety of states that the system can exhibit is smaller than the variety of states we can potentially conceive, then we say that the system is constrained, what means that the system cannot make a full use of the available freedom, because some internal or external laws do not allow certain combinations of values for the variables. The constraint reduces our uncertainty about the system state. Hence, the constraint,C, of the system can be defined as the difference between maximal and actual variety: C=Vmax −V. 560 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... The variety and constraint can be generalized to a probabilistic framework, where they are replaced by entropy and information, respectively. Let us suppose that we do not know the precise state, s, of a system, but only the probability distribution, P(s), of the system to be in state s.The generalization of the variety of the system can then be expressed as entropy H: H(P)=− s∈S P(s)·log(P(s)). Hreaches its maximum value when all states are equiprobable, that is, when we have no information to assume that one state is more probable than another one (and, in this case, entropy reduces to variety). Like variety, Hexpresses our uncertainty or ignorance about the system state. The following result, where we obtain maximal certainty (or complete information) about the state of the system, is straightforward. Lemma 1. The entropy vanishes, i.e., H=0, if and only if there exists a state s∈Ssuch that P(s)=1. As we have seen, the constraint reduces the uncertainty, that is, the difference between maximal and actual uncertainty. This difference can also be interpreted in a different way, as information, and historically Hwas introduced by Shannon [Shannon 48] as a measure of the capacity for information transmission of a communication channel. If we achieve information about the state of the system, then this information will reduce our uncertainty about the system state, by excluding (or reducing the probability of) a number of states. The information, I, we receive from this achievement is equal to the amount of uncertainty that is reduced, that is, the difference between the previous knowledge about the system and the latter one, I=Hbefore −Hafter. Although Shannon disagreed with the use of the term information to describe this measure, his theory came to be known as Information Theory. Since then, entropy has been used as a measure for a number of higher-order relational concepts, including complexity and organization, and it has been applied in several knowledge fields (as biology, ecology, psychology, sociology, and economics) where the use of complex systems is unavoidable. 3 Measuring the Entropy of Probabilistic P Systems At this point there is no doubt that a probabilistic P system (no mind the way to define the probability controlling the evolution of the system) can be a complex 561 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... system with the possibility to evolve along the time. Hence, all above parameters can be applied to measure the complexity of this kind of systems. Irrespective which is the chosen possibility to introduce probabilities in a membrane system (see [Obtulowicz and P˘aun 03] for a detailed study), if we look at the computations the system generates, the result is a tree with a probability measure over its nodes. Let us remember that over a rooted tree (an acyclic and connected graph where a vertex is remarked) we can define a direct relation between adjacent nodes. With respect to this relation, for every node xof the tree, we denote by Ch(x) the set of its children (that could be empty if xis a leaf) and we denote by Lthe set of all the leaves of the tree. Definition 2. Given a rooted tree G,withrootr, we say that a function P: V(G)→[0,1] is a probability function over Gif the following conditions are verified: –P(r)=1, –∀x∈V(G)(P(x)>0), –∀x∈V(G)(x/∈L→y∈Ch(x)P(y)=1). Definition 3. Aweightedtreeisapair(G, P), where Gis a rooted tree and P is a probability function over G. In this context, a probabilistic P system generates a rooted tree with a probability associated with the nodes labelled by configurations reachable in the computation, where the root of the tree is the initial configuration of the system, and the probability of every node is the probability to reach it from the previous configuration. This tree will be denoted by T(Π) (or briefly by T,if there is no confusion). The set of maximal branches of T(the computations of the P system) will be denoted by Comp(Π). If C∈Comp(Π), then we denote by Cithe i-th configuration of the computation C, therefore, C0is the initial configuration of the P system. We also denote by |C| the length of the computation C.(See[P´erez-Jim´enez and Sancho-Caparrini 02] for a formal definition of these concepts.) Definition 4. A Probabilistic P System (PPS for short) is a pair, (Π,P), where Πis a P system (of any kind), and Pis a probability function over T(Π). As a P system is a dynamic system where the probability of different evolutions depends on the actual state of the device, in order to capture its evolution, and to reflect its instant entropy, we propose two different concepts of entropy, aglobal one and a dynamic one, respectively. 562 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... In the case of the global entropy, we consider the set of possible computations of the PPS as the state space, that is, we study the different final states the P system can reach in its whole execution. To describe the entropy for the global case, we need to define a probability measure over Comp(Π). We achieve this by using the probability defined over the PPS: Definition 5. Given a PPS, (Π,P), we define a new probability measure over Comp(Π), that will be also denoted by P, as follows: P(C)=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩  i≤|C| P(Ci),if Cis a halting computation, lim n→|C|  i≤n P(Ci),otherwise. Note 6. Equivalently, P(C)=inf{i≤nP(Ci): n≤|C|}.Itiseasytocheck that the definition above is, in fact, a probability measure over Comp(Π). According to the previous definition of entropy and the probability defined in Comp(Π), the global entropy of the PPS is the following one. Definition 7. The global entropy of a PPS, (Π,P), is defined as: Hg(Π)=− C∈ Comp(Π) P(C)·log(P(C)). Note 8. Since limx→0x·log(x) = 0, we consider 0 ·log(0) = 0. The global entropy measures the uncertainty of the P system Πto evolve along the possible computations. Note that, if the P system has only one possible computation, C,thenP(C) = 1, hence, from Lemma 1, the entropy of the system vanishes; that is, there is no uncertainty about the evolution of the system. But, is there some way to define a measure reflecting the instantaneous entropy of the system? Next, we will try to define a more complex measure for the entropy of a PPS, where in some way the instant of its execution will be captured. But, previously, we need some definitions over trees. In a rooted tree, G, we can consider a depth function recursively defined as follows: dep(x)=0,if xis the root of G, dep(f(x)) + 1,otherwise, where, for every node xnot being the root, f(x) stands for the father of xin G. 563 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... The depth of Gis defined as dep(G)=max x∈Gdep(x). For every n≤dep(G), we define the n-level of Gas G|n={x∈G:dep(x)=n}, the leaves of Gas L={x∈G:Ch(x)=∅},Ln=L∩G|n,and Gn=G|n∪ k<n Lk. If x∈G,thenwedenotebyγxthe set of all nodes belonging to the only path from the root to x. If (G, P) is a tree with a probability function defined over its nodes, by using the paths defined above, we can define a new probability function (derived from P) over the levels of G. Lemma 9. Let (G, P )be a weighted tree. Then, for every n∈N, the following function, Pn, is a probability function over Gn: ∀x∈Gn,P n(x)=  y∈γx P(y). If (Π,P) is a PPS, then Tis a rooted tree, so we can apply all above definitions, obtaining the n-level entropy of the system. Definition 10. For every n∈N,then-level entropy of a PPS, (Π,P), is defined as: Hn(Π)=− C∈Tn Pn(C)·log(Pn(C)). The sequence {Hn(Π)}n∈Nis called dynamic entropy. Note 11. The dynamic entropy gives a measure of the evolution of a PPS that approximates the global entropy defined above, as it is shown in the next lemma. Lemma 12. For every PPS, (Π,P), it holds that {Hn(Π)}n∈Nis a monotonic non-decreasing sequence and lim n→∞ Hn(Π)=Hg(Π). Now we define the amount of information of the P system Πalong its evolution. Definition 13. The sequence of information of a PPS, (Π, P), is defined as: In(Π)=Hn(Π)−Hn+1(Π). 564 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... Whereas the global entropy defined above provides information about the global behavior of the system (watching all the possible computations like a whole), the dynamic entropy provides an indicator about its local behavior, and, a priori, no knowledge about the different evolution possibilities is needed. But as a practical tool to be used along the execution of a Probabilistic P System (where only one branch of the tree is in execution), we present the conditioned entropy, where only the actual state of the system is known. Note 14. If n∈N, then we will denote by Tn(C) the subset of Tnconsisting of all the configurations of Tnthat can be reached from C. Definition 15. Let n, j be natural numbers such that n≥j,let(Π,P)be a PPS, and C∈T.Then-th level of entropy of Π, supposed that Cis the configuration of Πat the j-th step of the execution, is defined as : Hn(Π|Π(j)=C)=  C∈Tn(C) Pn(C) Pj(C)·log( Pn(C) Pj(C)). 4 Conclusions In this paper we have applied entropy measures to Membrane Computing in order to give a new tool for obtaining information about the evolution of Probabilistic P Systems (no mind the used variant). Only a first approach to the application of Information Theory (a fundamental tool in the study of complex systems) to the study of Membrane Computing has been presented. We think that a deeper study of the descriptive complexity (at both structural and operational levels) of the devices generated in this model can be of a great value. The interpretation of P systems as complex systems, as well as their demonstrated power in the efficient resolution of hard problems, suggests a promising direction for the representation of very varied complex systems that, at the moment, lack an effective mathematical formalization. In this way, some new questions arise: is it possible to represent complex systems (in structure and function) within this model? If so, can a P system be defined where some kind of emergency (properties not initially present in the system) arises? Acknowledgment The support for this research through the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, is gratefully acknowledged. 565 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ... References [Hall and Fagan 80] Hall A.D., Fagan R.E.: “Definition of a system”; “The General Theory of Systems Applied to Management and Organization” (D.M. Jamieson, G. Chen, L.L. Schkade, C.H. Smith, eds.), Intersystems Publications, Seaside CA (1980), 217–243 [Obtulowicz and P˘aun 03] Obtulowicz A., P˘aun Gh.: “(In search of) Probabilistic P systems”; BioSystems, 70, 2 (2003), 107–121 [P˘aun 00] P˘aun Gh.: “Computing with membranes”; Journal of Computer and System Sciences, 61, 1 (2000), 108–143 [P´erez-Jim´enez and Sancho-Caparrini 02] P´erez-Jim´enez M.J., Sancho-Caparrini F.: “A formalization of basic P systems”; Fundamenta Informaticae, 49, 1–3 (2002), 261–272 [Shannon 48] Shannon C.E.: “A mathematical theory of communication”; Bell System Technical Journal, 27 (1948), 379–423 and 623–656 566 Cordon-Franco A., Sancho-Caparrini F.: A Note on Complexity Measures ...