Graphics and P Systems: Experiments with JPLANT

Graphics and P Systems: Experiments with JPLANT Elena Rivero-Gil, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain E-mails: [email protected], [email protected], [email protected] Summary. The hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes and objects increases. In this paper we present a new software tool, called JPLANT, for computing and representing the evolution of a P system model with membrane creation. We also present some experiments performed with JPLANT and point out new lines for the research in computer graphics with membrane systems. 1 Introduction Since A.R. Smith [12] proposed the Lindenmayer systems (L-systems) [5] as a tool for synthesizing realistic images of plants, many efforts have been done for bridging the theory of formal languages and computer graphics. In [2, 3], a first membrane-based device for computer graphics was presented. It was a hybrid model between L-systems and membrane computing and it used concepts very close to the L-systems model. Later, in [10], a new approach was presented for representing the development of higher plants with P systems. It was based on a type of P systems with membrane creation and it was entirely developed with membrane computing techniques. The basic idea was to consider the growing of the structure the membranes in a P system with membrane creation. By definition, the structure of membranes in a cell-like P system is a tree. In P systems with membrane creation, new membranes can be created inside the existing membranes and this produces the expansion of the structure of membranes by increasing the depth of the branches. With an appropriate interpretation of the objects inside the membranes, the membrane structure can be represented as a tree which evolves in time and the length and width of the branches can grow in a similar way to real plants. In [11], the study started at [10] was completed by adding stochastic rules to the P system. In this case, the non-deterministic choice 242 E. Rivero-Gil et al. of different rules produces different configurations of the P systems and hence, different graphical representations. The hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes and objects increases. For going on with the study of the relation between P systems and computer graphics it was necessary to develop a software able to deal with complex P systems and represent graphically its evolution in time. In this paper we present such a software, JPLANT, which computes the first configurations of a computation and draws the corresponding graphical representation. This software is a very useful tool for the experimental research of the graphical representation of P systems. We show several experiments and open new research lines for exploring the possibilities of P systems. The paper is organized as follows: Section 2 recall the restricted model of P systems with membrane creation used for the graphical design. Section 3 gives a brief presentation of the software JPLANT and the next section shows several experiments. The paper finishes with some conclusions and lines for future research. 2 P Systems with Membrane Creation Membrane computing is a branch of natural computing which abstracts from the structure and the functioning of the living cell. In the basic model, membrane systems (also frequently called P systems) are distributed parallel computing devices, processing multisets of symbol-objects, synchronously, in the compartments defined by a cell-like membrane structure1. In this paper we will consider P systems which make use of membrane creation rules, which was first introduced in [4, 6]. However, our needs are far simpler than what the models found in the literature provide. This is the reason why we introduce the new variant of restricted P systems with membrane creation. A restricted P system with membrane creation is a tuple Π= (O, µ, w1, . . . , wm, R) where: 1. Ois the alphabet of objects. There exist two distinguished objects, Fand W that always belong to the alphabet of any P system considered below. 2. µis the initial membrane structure, consisting of a hierarchical structure of m membranes (all of them with the same label; for the sake of simplicity we omit the label). 3. w1, . . . , wmare the multisets of objects initially placed in the mregions delimited by the membranes of µ. 4. Ris a finite set of evolution rules associated with every membrane, which can be of the two following kinds: a) a→v, where a∈Oand vis a multiset over O. This rule replaces an object apresent in a membrane of µby the multiset of objects v. 1A detailed description of P systems can be found in [9] and updated information in [13]. Graphics and P Systems: Experiments with JPLANT 243 b) a→[v], where a∈Oand vis a multiset over O. This rule replaces an object apresent in a membrane of µby a new membrane with the same label and containing the multiset of objects v. A membrane structure together with the objects contained in the regions defined by its membranes constitute a configuration of the system. A transition step is performed applying to a configuration the evolution rules of the system in the usual way within the framework of membrane computing, that is, in a nondeterministic maximally parallel way; a rule in a region is applied if and only if the object occurring in its left–hand side is available in that region; this object is then consumed and the objects indicated in the right–hand side of the rule are created inside the membrane. The rules are applied in all the membranes simultaneously, and all the objects in them that can trigger a rule must do it. When there are several possibilities to choose the evolution rules to apply, non-determinism takes place. 2.1 Graphical Representation In this section we show how to use, through a suitable graphical representation, restricted P systems with membrane creation to model branching structures. The key point of the representation relies on the fact that a membrane structure is arooted tree of membranes, whose root is the skin membrane and whose leaves are the elementary membranes. Thus, this seems a suitable frame to encode the branching structure. Let us suppose that the alphabet Oof objects contains the objects Fand W, and let us fix the lengths land w. A simple model to graphically represent a membrane structure is to make a depth-first search of it, drawing, for each membrane containing the object F, a segment of length m×l, where mis the multiplicity of F. If the number of copies of Fin a membrane increases along the computation, the graphical interpretation is that the corresponding segment is lengthening. Analogously, the multiplicity of the symbol Wspecify the width of the segments to be drawn as follows: if the number of objects Wpresent in a membrane is n, then the segment corresponding to this membrane must be drawn with width n×w. Each segment is drawn rotated with respect to the segment corresponding to its parent membrane. In order to determine the rotation angle we need to fix a third parameter δ. This angle δtogether with the length land the width wwill determine the picture of the P system. In order to compute the rotation angle of a segment with respect to its parent membrane we consider two new objects that can appear in the alphabet: + and −. The rotation angle will be n×δ, where nis the multiplicity of objects “+” minus the multiplicity of objects “−” in the membrane. That is, each object “+” means that the rotation angle is increased by δwhereas each object “−” means that it is decreased by δ. 244 E. Rivero-Gil et al. Inside the membranes other objects can appear that do not have geometrical interpretation. They are related to the development of the graph in time. For a better understanding let us consider the following example: let Π1be the restricted P system with membrane creation such that Fig. 1. First four configurations •The alphabet of objects is O={F, W, Bl, Bs, Br, L, L1, E, +,−}. •The initial membrane structure together with the initial multiset of objects is [F2W BlBsL1E]. •The rules are: Bl→[+ FWBlBsL E]L→L F Bs→[FWBlBrL1E]L1→L1F2 Br→[−FWBlBsL E]E→E W In this system, the object Bsrepresents the straight branches to be created, whereas the objects Bland Brrepresent branches to be created rotated to the left and to the right, respectively. The objects Fand Wwill determine the length and the width of the corresponding branch. The objects L,L1and Edo not have a graphical interpretation; they can be considered as seeds for growing the branch in length and width. Graphics and P Systems: Experiments with JPLANT 245 The initial configuration consists of one membrane which contains two copies of Fand one copy of W. If we consider the parameters l,wand δ, then the graphical representation of this initial configuration is a single segment of length 2 ×land width w. In the first step, the objects Bland Bscreate new membranes, so the picture of this configuration consists on three segments. The new membrane created by Bsdoes not contains objects + or −and then the corresponding segment is not rotated with respect to the segment that represents the skin. On the other hand, the membrane created by Blcontains one object +, so its segment will be rotated an angle δwith respect to its parent membrane. Notice also that the evolution of the objects L1and Ehas modified the number of objects Fand Win the skin, so in this new picture, the segment corresponding to the skin has length 4 ×land width 2 ×w. Figure 1 shows the graphical representation of the first four configurations where we fix a bottom-up orientation and an angle δof 15 degrees. 2.2 Stochastic Versus Non-deterministic P Systems The non-determinism is one of the main features of P systems and the possibility of reaching different configurations leads us to consider different graphical representations in the evolution of a P system. One possible way to formalize the probability of obtaining one or other configuration is via stochastic P systems. Several alternatives to incorporate randomness into membrane systems can be found in the literature (see [1, 7, 8] and the references therein). One of them is to associate each rule of the P system with a probability. Thus, to pass from a configuration of the system to the next one we apply to every object present in the configuration a rule chosen at random, according to those probabilities, among all the rules whose left–hand side coincides with the object2. For example, let us consider Π2the following restricted P system with membrane creation: •The alphabet of objects is O={F, W, Bl, Bs, Br, L, L1, E}. •The initial membrane structure together with the initial multiset of objects is [F2W BlBsL1E]. •The rules are: Bl 1/2 −−→ [+ FWBlBsL E]L→L F Bl 1/2 −−→ [−FWBlBsL E]L1→L1F2 Br 1/2 −−→ [+ FWBlBsL E]E→E W Br 1/2 −−→ [−FWBlBsL E]Bs→[FWBlBrL1E] 2This idea was presented in [11]. 246 E. Rivero-Gil et al. Fig. 2. Four configurations after the second step There exist two rules for the evolution of the object Bland two possibilities for the evolution of the object Br. The probability for each choice is 1/2. Notice that we do not make explicit the probability of the rule when this is one. Figure 2 shows four different configurations after the second step of this P system with the angle δ= 15. 3 JPLANT In order to avoid the heavy hand-made computation for the graphical representation a new software tool has been designed. In this paper we present JPLANT 3, which computes the first configurations of a computation of a restricted P system with membrane creation and draws the corresponding graphical representation of the configurations of such computation. JPLANT has been written in Java and it has a nice intuitive user-friendly graphical interface. The initial configuration and the set of rules are provided in plain text mode. The right syntax of the initial configuration and the rules are checked before starting the computation. The generation of a new configuration is driven by the user which can choose between jumping to a configuration Nor generating (and drawing) at each time the next configuration. The software tool is thought as a drawing tool so the computed new configurations are not showed to the user in the text mode. The output is a picture with a set of connected segments drawn according with the rules described in Section 3The software is available from [13]. Graphics and P Systems: Experiments with JPLANT 247 2. For each new configuration, a new picture is drawn, so the output of this tool is a sequence of pictures which can be saved in several computer graphic formats. The graphical representation of one configuration is not unique. It depends on the parameters l,wand δwhich determine the length and width of the segments as well as the rotation angle with respect to the segment corresponding to the parent membrane. Such parameters are the input of the tool and they must be also provided by the user with the initial configuration and the rules. The current version of JPLANT includes the ability of load and save files with the input data and save the generated pictures and also provide color to the pictures. The color is one of the basic tools in the graphical design. In the current version, the color of the segment associated with each membrane is not associated with any object inside the membrane. In this way, we cannot change the color of a membrane by the analysis of the membrane structure of a computation. Nonetheless, JPLANT provides the ability of giving color to the generated picture. It is an ability which is not associated with the P system which generates the picture, but it is a powerful tool in order to get realistic representations. 4 Applications Next we illustrate the possibilities of JPLANT with some examples. 4.1 Polygons and Spirals Polygons and spirals can be considered a very special case of branching structures. They consists of a connected set of segments where a vertex only connect two segments. From a membrane computing point of view, this means that each membrane in a configuration only contains one membrane. Polygons A first example of figures built with P systems are regular polygons. In such polygons the length of the side is constant and the angle of deviation from the previous side is also constant. A simple calculus shows us that a deviation of δ= 360/n degrees allows us to built a regular polygon of nsides. Figure 3 shows regular polygons of n= 10 and n= 12 sides obtained with δ= 36 and δ= 30 degrees. Obviously the number of steps are 10 and 12 respectively. The P system is the following Initial configuration: [F W H] Rule: H→[−FWH] 248 E. Rivero-Gil et al. Fig. 3. 10-polygon and 12-polygon Spirals In mathematics, a spiral is a curve which emanates from a central point, getting progressively farther away as it revolves around the point. The concise mathematical definition is the locus of a point moving at constant speed whose distance from a fixed point increases at a specific rate. An Archimedean spiral (a spiral named after the 3rd-century-BC Greek mathematician Archimedes) is the locus of points corresponding to the locations over time of a point moving away from a fixed point with a constant speed along a line which rotates with constant angular velocity. Equivalently, in polar coordinates (ρ, ω) it can be described by the equation ρ=a+bω with real numbers aand b. Archimedes described such a spiral in his book On Spirals. It can be represented with the following P system: Initial configuration: [FnWHL] Rules: H→[−FnWLH] L→LF Figure 4 shows the representation of such Archimedes spiral for n= 5, length of F= 0.01, width W= 1.0, angle δ= 15 and step 120. The logarithmic spiral is a special kind of spiral curve which often appears in nature. It was first described by Descartes and extensively investigated by Jakob Bernoulli, who called it Spira mirabilis, “the marvelous spiral”. Its equation in polar coordinates is ρ=cω. It can be approximated by the P system Initial configuration: [FnWHL] Rules: H→[−FnWLH] L→LM1F M1→M2 . . . Mi−1→Mi Mi→L Graphics and P Systems: Experiments with JPLANT 249 Fig. 4. Archimedes’ spiral Fig. 5. Logarithmic spiral Figure 5 shows the representation of such logarithmic spiral for n= 10, i= 7, length of F= 0.001, width W= 1.0 angle δ= 30 and step 40. 4.2 Friezes Another application of JPLANT for the graphical representation of restricted P systems with membrane creation is the design of friezes. With the appropriate interpretation of the symbols, the following P system can be represented as a frieze based on right angles which has a flavor of Greek friezes. It can be extended horizontally in a non bounded way.