Solving the BINPACKING Problem by Recognizer P Systems with Active Membranes

Solving the BINPACKING Problem by Recognizer P Systems with Active Membranes Mario J. P´ EREZ-JIM´ ENEZ, Francisco Jos´e ROMERO-CAMPERO Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {Mario.Perez, Francisco-Jose.Romero}@cs.us.es Abstract. In this paper we present an effective solution to the BINPACKING problem using a family of recognizer P systems with active membranes, input membrane and external output. The analysis of the solution presented here will be done form the point of view of complexity classes. 1 Introduction P systems are an emergent branch in the field of Natural Computing. This unconventional model of computation is presented as a kind of distributed parallel computing model and it is based upon the observation that the processes which take place in the complex structure of a living cell can be considered as computations. Since Gh. P˘aun introduced it in [2] several variants have been considered from different approaches. A fairly complete compendium about P systems can be found in [3]. Many of the proposed variants have been proved to be computational complete,their computational power is that of Turing machines; besides some variants of P systems have been proved to be computational efficient, they have been shown to be able to solve NP-complete problems in polynomial time (see [3] Chapter 7). The solution presented here has been designed through a family of recognizer P systems with active membranes, input membrane and external output. In particular, P systems with active membranes are studied in [3], section 7.2. We have followed the ideas and schemes used to solve others numerical NP-problems as the Subset–Sum in [9] and the Knapsack problem in [10]. Due to the strong similarities of the design of these solutions the idea of a cellular programming language seems possible as it is suggested in [12]. The analysis of the presented solution will be done from the point of view of the complexity classes. A complexity class for a model of computation is a collection of problems that can be solved (or languages that can be decided) by some devices of this model with similar computational resources. We will study the complexity of the proposed solution within the framework of the complexity classes in P systems studied in [7] and [8]. The paper is organized as follows: Section 2 recalls recognizer P systems with active membranes, input membrane and external output. In section 3 the complexity classes for P systems are briefly introduced. Sections 4, 5 and 6 show a cellular solution to the 414 BINPACKING problem. In section 7 we use a CLIPS simulator for recognizer P systems with acive membranes to show a session for the BINPACKING problem. Conclusions are given in section 8. 2 Recognizer P systems with Active Membranes, Input Membrane and External Output Definition 2.1 A decision problem, X, is a pair (IX, θX)such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function over IX. Definition 2.2 AP system with input is a tuple (Π,Σ, iΠ), where: •Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets M1, . . . , Mpassociated with them. •Σis an (input) alphabet strictly contained in Γ. •The initial multisets are over Γ−Σ. •iΠis the label of a distinguished (input) membrane. Definition 2.3 Let (Π,Σ, iΠ)be a P system with input. Let Γbe the working alphabet of Π,µthe membrane structure and M1, . . . , Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of (Π,Σ, iΠ) with input mis (µ0, M0), where µ0=µ,M0(j) = Mj, for each j6=iΠ, and M0(iΠ) = MiΠ∪m. The computations of a P system with input m∈M(Σ), a multiset over Σ, are defined in a natural way. The only novelty is that the initial configuration must be the initial configuration of the system associated with the input multiset m∈M(Σ). In the case of P systems with input and with external output, the concept of computation is introduced in a similar way but with a slight variant. In the configurations, we will not work directly with the membrane structure µbut with another structure associated with it including, in some sense, the environment. Definition 2.4 Let µ= (V(µ), E(µ)) be a membrane structure. The membrane structure with external environment associated with µis the rooted tree Ext(µ)such that: (a)the root of the tree is a new node that we will denote env;(b)the set of nodes is V(µ)∪ ©envª; and (c)the set of edges is E(µ)∪©{env, skin}ª. The node env is called external environment of the structure µ. Note that we have only included a new node representing the environment which is only connected with the skin, while the original membrane structure remains unchanged. In this way, every configuration of the system informs about the contents of the external environment. Definition 2.5 Arecognizer P system is a P system with input, (Π,Σ, iΠ), and with external output such that: 1. The working alphabet contains two distinguished elements YES, NO. 415 2. All its computations halt. 3. If Cis a computation of Π, then either some object YES or some object N0 (but not both) mush have been released into the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object YES (respectively, N0) appears in the external environment associated to the corresponding halting configuration of C. This recognizer systems are specially suitable when trying to solve decision problems. In this paper we will deal with recognizer P-Systems with Active Membranes, Input Membrane and External Output. Let’s remember that a P system with Active Membranes is a tuple: Π = (Σ, H, µ, ω1, . . . , ωm, R) where: 1. m≥1, is the initial degree of the system; 2. Σ is the alphabet of symbol-objects; 3. His a finite set of labels for membranes; 4. µis a membrane structure, of mmembranes, labelled (not necessarily in a one-to-one manner) with elements of H; 5. ω1, . . . , ωmare strings over Σ, describing the initial multisets of objects placed in the mregions of µ; 6. Ris a finite set of evolution rules, of the following forms: (a) [ a→ω]α hfor h∈H,α∈ {+,−,0},a∈Σ, ω∈Σ∗,object evolution rules: This is an object evolution rule, associated with a membrane labelled with hand depending on the polarity of that membrane, but not directly involving the membrane. (b) a[ ]α1 h→[b]α2 hfor h∈H,α1, α2∈ {+,−,0},a, b ∈Σ, communication rules (send in rules): An object from the region immediately outside a membrane labelled with his introduced in this membrane, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. (c) [ a]α1 h→b[ ]α2 hfor h∈H,α1, α2∈ {+,−,0},a, b ∈Σ, communication rules (send out rules): An object is sent out from membrane labelled with hto the region immediately outside, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. (d) [ a]α h→bfor h∈H,α∈ {+,−,0},a, b ∈Σ, dissolving rules: A membrane labelled with his dissolved in reaction with an object. The skin is never dissolved. (e) [ a]α1 h→[b]α2 h[c]α3 hfor h∈H,α1, α2, α3∈ {+,−,0},a, b, c ∈Σ, division rules for elementary membranes: An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects and their polarities. 416 These rules are applied according to the following principles: •All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non deterministic way), but any object which can evolve by one rule of any form, should evolve. •If a membrane is dissolved, its content (multiset and internal membranes) is left free in the surrounding region. •If at the same time a membrane his divided by a rule of type (e) and there are objects in this membrane which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, and then the division is produced. Of course, this process takes only one step. •The rules associated with membranes labelled with hare used for all copies of this membrane. At one step, a membrane labelled with hcan be the subject of only one rule of types (b)-(e). Let us denote by AM the class of language recognizer P systems with active membranes using 2-division (see [3], section 7.2). 3 The complexity class PMCF Roughly speaking, a computational complexity study of a solution for a problem is an estimation of the resources (time, space, ...) that are required through all the processes that take place in the way from the bare instance of the problem up to the final answer. The first results about “solvability” of NP–complete problems in polynomial time (even linear) by cellular computing systems with membranes were obtained using variants of P systems that lack an input membrane. Thus, the constructive proofs of such results need to design one system for each instance of the problem. If we wanted to perform such a solution of some decision problem in a laboratory, we will find a drawback on this approach: a system constructed to solve a concrete instance is useless when trying to solve another instance. This handicap can be easily overtaken if we consider a P system with input. Then, the same system could solve different instances of the problem, provided that the corresponding input multisets are introduced in the input membrane. Instead of looking for a single system that solves a problem, we prefer designing a family of P systems such that each element decides all the instances of ”equivalent size”, in certain sense. Let us now introduce some basic concepts before the definition of the complexity class itself. Definition 3.1 Let Lbe a language, Fa class of P systems with input and Π= (Π(n))n∈N+a family of P systems of F. A polynomial encoding of Lin Πis a pair (g, h)of polynomial-time computable functions g:L→[ n∈N+ IΠ(n)and h:L→N+ such that for every u∈Lwe have g(u)∈IΠ(h(u)). 417 Lemma 3.1 Let L1⊆Σ1and L2⊆Σ2be languages. Let Fbe a class of P systems with input and Π= (Π(n))n∈N+a family of P systems of F. If r: Σ1→Σ2is a polynomial time reduction from L1to L2, and (g, h)is a polynomial encoding of L2in Π, then (g◦r, h ◦r)is a polynomial encoding of L1in Π. Definition 3.2 Let Fbe a class of recognizer P systems, f:N+→N+a total recursive function, and X= (IX, θX)a decision problem. We say that X∈MCF(f)if there exists a family, Π= (Π(n))n∈N+, of P systems such that: •Πis F–consistent: ∀n∈N+,Π(n)∈ F. •Πis uniform: there exists a deterministic Turing machine that from n∈N+constructs Π(n)in polynomial time. •There exists a polynomial encoding (g, h)from IXto Πverifying: – Π is f–bounded, regarding to (g, h). For each u∈IX, all computations of Π(h(u)) with input g(u)halt in, at most, f(|u|)steps. – Π is X–sounded, regarding to (g, h). For each u∈IX, if every computation of Π(h(u)) with input g(u)is an accepting computation, then θX(u) = 1. – Π is X–complete, regarding to (g, h). For each u∈IX, if θX(u) = 1, then every computation of Π(h(u)) with input g(u)is an accepting computation. Remark 3.1 In the above definition we have imposed every P system Π(n)to be confluent, in the following sense: for every input m, either every computation of Π(n)with input mis an accepting computation, or every computation of Π(n)with input mis a rejecting computation. Definition 3.3 The polynomial complexity class associated with a collection of recognizer P systems, F, is defined as follows: PMCF=[ fpolynomial MCF(f) Proposition 3.1 Let Fbe a class of P systems with input. Let X, Y be problems such that Xis reducible to Yin polynomial time. If Y∈PMCF, then X∈PMCF. 4 The BINPACKING Problem The BINPACKING problem can be stated as follows: Given a set A={s1, . . . , sn}, a weight function ω:A→Nand two constants b∈N,c∈Ndecide whether or not there exists a partition of Ainto bsubsets such that their weights do not exceed c. 418 This problem can be seen as the situation when we have nitems, bbins of capacity c and we have to introduce the items in the bins. We will represent the instances of the problem using tuples of the kind (n, (ω1, . . . , ωn), b, c), where nis the number of items, (ω1, . . . , ωn) are the weights, bis the number of bins and ctheir capacity. We will face the resolution of this problem via a brute force algorithm, in the framework of recognizer P systems with active membranes using 2-division, without cooperation nor priority among rules. Our strategy will consist in: •For each bin: –Generation stage: Membrane division is used until a specific membrane for each subset Sof the remaining items is obtained. –Calculation stage: In each membrane the weight of the associated subset is calculated. –Checking stage : The condition ω(S)≤cis checked for every subset S⊆A. –Transition stage: If the associated subset satisfies ω(S)≤cthen we introduce these items in this bin and we repeat the process with the remaining items and bins; otherwise the membrane is dissolved. •Output stage: The answer is released into the environment according to the results in the checking stage for each bin. Now we construct a family of recognizer P systems with active membranes using 2- division solving the BINPACKING problem. Let us consider a polynomial bijection, h i, between N3and N(e.g. hx, y, zi= hhx, yi, zi, induced by the pair function hx, yi= (x+y)·(x+y+ 1)/2 + x). The family presented here is Π={(Π(hn, b, ci),Σ(n, b, c), i(n, b, c)) : (n, b, c)∈N3} For each element of the family, the input alphabet is Σ(n, b, c) = {s1, . . . , sn, z1, . . . , zn}, the input membrane is i(n, b, c) = 2, and the P system Π(hn, b, ci) = (Γ(n, b, c),{1,2}, µ, M1,M2, R) is defined as follows: •Working alphabet: Γ(n, b, c) = {zijk, sijk, Zijk, Sijk, z0, z, w, W, gl, T, tm, D, D, ˆ D, G, G1, fr, neg, de, Y ES, NO : 1 ≤i≤b, −1≤j≤n, 1≤k≤n, 0≤l≤2n+ 1,0≤m≤2n+ 1} •Membrane structure: µ= [1[2]2]1 •Initial Multisets: M1={f1},M2={f1, g0, Dc} •The set of evolution rules, R, consists of the following rules: 1. [ sk→s1, k, k ]0 2; [ zk→z1, k, k ]0 2,1≤k≤n These rules initialize the algorithm. The objects of type sand zwill have three subindixes. The first one, 1 ≤i≤b, will represent the number of the bin where the item represented by this object can be added. The second one, −1≤j≤n 419 will denote its position in the stack to be added in the current bin; if second subindixe is -1 then this item has not been chosen to be added in the bin. The third one, 1 ≤k≤nwill be use to show for which item this object is used to represent its weight. 2. [ zi, 1, k ]0 2→[z]+ 2[zi, −1, k ]0 2,1≤k≤n , 1≤i≤b−1 The goal of these rules is to generate one membrane for each subset of the remaining items that can be added in the current bin. When the object zi, 1, k is present in a neutrally charged membrane with label 2 it means that the system has to decide whether or not the item number kis chosen for the subset to be added in the bin number i. So the membrane is divided into two membranes: one positively charged which will represent the subset where the item number kis chosen to be introduced in the bin, the object zappears in this membrane; and the other one will be negatively charged and will represent the subset where the item number kis not added in the bin, so we set the second subindixe to −1, zi, −1, k. 3. [ si, 0, k →w]+ 2,1≤k≤n, 1≤i≤b−1 The presence of the objects si, 0, k in a positively charged membrane with label 2 means that the item number kis added to the subset associated to the membrane. The multiplicity of the object s·,·, k encodes the weight of the item k and the multiplicity of the object wencodes the weight of the subset associated to the membrane.So when an item is added to the subset associated to the membrane the objects si, 0, k evolve to w. 4. [ z]+ 2→][ ]0 2 The element zis used to change the polarization of the membranes with label 2 from positive to neutral. 5. [ si, j, k →si, j−1, k]0 2; [ zi, j, k →zi, j−1, k]0 2; 0 ≤j≤n, 1≤k≤n, 1≤i≤ b−1 Once the item analyze has been or not introduced to the bin these rules update the stack of items by rotating the second subindixes of the objects of type s and z. 6. [ gi→gi+1 ]0 2; [ gi→gi+1 ]+ 2; 0 ≤i≤2n−1 The objects giare counters used in the generation stage. 7. [ g2n→g2n+1 , t0]0 2; [ g2n→g2n+1 , t0]+ 2; The generation stage takes 2nsteps. The object g2nwill produce the objects g2n+1 and t0which will begin the preparation for the checking stage. 8. [ g2n+1 ]0 2→][ ]− 2; The item g2n+1 will change the polarization of the membranes with label 2 from neutral to negative. 9. [ w→W]− 2 In the preparation for the checking stage the objects ware renamed to Win order to avoid conflicts with the previous stage. 10. [ si, −1, k →Si, k, k ]− 2; [ zi, −1, k →Zi, k, k ]− 2; 1 ≤i≤b−1,1≤k≤n The objects si, −1, k and zi, −1, k are renamed to Si, −1, k and Zi, −1, k before the checking stage in order to avoid conflicts with the previous stage. 420 11. [ D→D , ˆ D]− 2 The multiplicity of the objects Drepresents the capacity of the bins. In the checking stage we have to check if the weight of the subset introduced in the current bin exceeds or not its capacity. At the beginning of this stage the objects Dproduce the objects Dand ˆ D. The objects ˆ Dwill be used in the checking stage of the current bin and the objects Dwill keep the capacity of the bins so this information can be used later in the computation. 12. [ ˆ D]− 2→][ ]0 2; [ W]0 2→][ ]− 2 With these rules the system checks whether or not the weight of the subset introduced in the bin exceeds its capacity. 13. [ ti→ti+1 ]− 2; [ tj→tj+1 ]0 2; 0 ≤i≤2c−1,1≤j≤2c−1 The objects tiare counters used in the checking stage. 14. [ t2c→t2c+1, G, z0]− 2; [ t2c;→t2c+1, G, z0]0 2; The checking stage takes 2csteps. The objects t2cwill produce the objects t2c+1, G and z0which will begin the transition to the next bin. 15. [ t2c+1 ]− 2→][ ]+ 2; [ t2c+1 ]− 2→][ ]+ 2; The object t2c+1 changes the polarization of membranes with label 2 from negative to positive and the transition stage begins. 16. [ W]+ 2→] If there are still objects Wwhen the checking stage has finished it means that the multiplicity of objects Wexceeded the multiplicity of objects ˆ D. So the weight of the subset introduced in the bin exceeded its capacity, that is this is not a possible solution to the problem and the corresponding membrane is dissolved. 17. [ ˆ D→]]+ 2 The remaining objects ˆ Dare ”erased” in the transition stage. 18. [ D→D]+ 2 The objects Dare renamed to Dso they can be used in the computation for the next bin. 19. [ Si, k, k →si+1, k, k ]+ 2; [ Zi, k, k →zi+1, k, k ]+ 2; 1 ≤i≤b−2; 1 ≤k≤n The objects Si, k, k and Zi, k, k are renamed to si+1, k, k and zi+1, k, k so they can be used in the computation for the next bin. 20. [ G→G1]+ 2; [ G1→g1]0 2 These rules produce the object g1that will be used as counter in the generation stage of the next bin. 21. [ z0→z]+ 2 The object zis produced to finish the transition stage. 22. [ Sb−1, k, k →w]+ 2; [ Zb−1, k, k →]]+ 2; 1 ≤k≤n These rules introduce all the remaining items in the last bin. 23. [ fi→fi+1 ]0 2; [ fi→fi+1 ]+ 2; [ fi→fi+1 ]− 2; 0 ≤i≤2nb + 2cb + 5b−2n− 2c−5 The objects fiare counters that will show when the checking stage for the last bin must begin. 421 24. [ f2nb+2cb+5b−2n−2c−4→neg, T, d0]+ 2; This rule will force the system to skip the generating stage for the last bin and will force the checking stage begin. 25. [ T→t0]0 2; [ neg ]0 2→][ ]− 2 These rules initialize the checking stage for the last bin. 26. [ di→di+1]0 2,[di→di+1]− 2,[d2c+3 ]0 2→Y ES ; 0 ≤i≤2c+ 2 The objects diare counters in the membranes with label 2 that eventually will produce the answer YES. 27. [ di→di+1 ]0 1; [ d2nb+2cb+5b−2n+3 →NO ]0 1 The objects diare counters in the skin that will eventually produce the answer NO. 28. [ Y ES ]0 1→Y ES[ ]+ 1; [ NO ]0 1→Y ES[ ]− 1 These rules released the answer into the environment. Note that if the answer of the system must be YES this object will appear in the skin one step before the object NO so no conflict occurs. 5 An Overview of the Computation First of all we must define a polynomial encoding of the Binpacking problem in the family Πin order to study the complexity of the problem with respect to it. Given an instance u= (n, (ω1, . . . , ωn), b, c) of the Binpacking problem, we define h(u) = hn, b, ci(recall the bijection mentioned in the previous section) and g(u) = {z1, . . . zn, sω1 1, . . . , sωn n}. Now we will informally describe how the system Π(h(u)) with input g(u) works. In the first step of the computation, the rules [ sk→s1, k, k ]0 2; [ zk→z1, k, k ]0 2are applied to initialize the computation. The first subindixe of these objects represents the bin we are dealing with. For each bin i, for 1 ≤i≤b−1, the generation and calculation stages take place in parallel, following the instructions from the rules in 1 - 7. This two stages end when the object g2n+1 set the polarization of the membrane to negative. We generate every subset of the remaining items, associating each subset to a single working membrane. Let us introduce the concept of subset associated with an internal membrane through the following recursive definition: •The subset associated with the initial membrane is the empty one. •When an object zi, ·, k does not appears in a inner membrane it means that the k-th item of Ahas been introduced in the bin number i. In the other hand when an object zi, −1, k appears in an inner membrane, it means that the k-th item of Ahas been left out of the bin number iand so it can be introduced in the following bins. •When a division rule is applied, the two newborn membranes inherit the associated subset form the original membrane. As we have mentioned above, the two first stages are carried out in parallel. Indeed, there is only a gap of one step of computation between the moment when an item is added to the associated subset and the moment when the new weight of the subset is updated. For example, for the item number 1 which is represented by the objects s1and 422 Configuration number: 25 [environment [multiset YES ,]] [skin [children ] [label 1] [polarity +] [multiset , NO , YES , ]] The system has reached a halting configuration in the step number 25 and the element YES has been released into the environment. 8 Conclusions In this paper we have presented an effective solution for the BINPACKING problem through a family of recognizer P systems with active membranes. This has been done in the framework of complexity classes in cellular computing with membranes. The design presented here is very similar to the solutions to numerial NP-complete problems studied in [9], [10] and [12]. The strong similarities in their designs show that the idea of a cellular programming language is posible, indicating some “subroutines” that can be used in a variety of situations and therefore could be useful for attacking new problems in the future. As an example of the usefulness of the subroutines outlined in [12], let us see how the design of the solutions for the BINPACKING would look like: BINPACKING for i=1, . . . , b-1 do gen −subsets(ni) calc −weight(ni) rename check −weight marker −leq counter(n) clean −dissolve end for. calc −weight(nb) rename check −weight marker −leq counter(n) clean −dissolve detector answer The CLIPS simulator for P systems presented in [11] is a very useful tool that has helped to debug the design and to understand better how the P systems from the family Πwork. Acknowledgement. This work is supported by the Ministerio de Ciencia y Tecnolog´ıa of Spain, by the Plan Nacional de I+D+I (2000–2003) (TIC2002-04220-C03-01), 429 cofinanced by FEDER funds, and by a FPI fellowship (of the second author) from the University of Seville. References [1] Cord´on-Franco, A., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Sancho- Caparrini, F.: A Prolog simulator for deterministic P systems with active membranes, New Generation Computing, in press. [2] P˘aun, Gh.: Computing with membranes, Journal of Computer and Systems Sciences, 61, 1 (2000), 108–143. [3] P˘aun, Gh.: Membrane Computing. An Introduction, Springer-Verlag, 2002. [4] P˘aun, Gh., Rozenberg, G.: A guide to membrane computing, Theoretical Computer Sciences, 287 (2002), 73–100. [5] P˘aun, Gh., Rozenberg, G., Salomaa, A.: Membrane computing with external output, Fundamenta Informaticae, 41, 3 (2000), 313–340. [6] P´erez-Jim´enez, M.J., Romero-Jim´enez, A., Sancho-Caparrini, F.: Solving VALIDITY problem by active membranes with input, Proceedings of the Brainstorming Week on Membrane Computing, M. Cavaliere, C. Martin-Vide, and Gh. P˘aun (eds), Report GRLMC 26/03, 279–290. [7] P´erez-Jim´enez, M.J., Romero-Jim´enez, A., Sancho-Caparrini, F.: Teor´ıa de la Complejidad en modelos de computacion celular con membranas, Editorial Kronos, 2002. [8] P´erez-Jim´enez, M.J., Romero-Jim´enez, A., Sancho-Caparrini, F.: A polynomial complexity class in P systems using membrane division, Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, and Gy. Vaszyl (eds.), 2003, 284–294. [9] P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A.: Solving the Subset-Sum problem by active membranes, New Generation Computing, in press. [10] P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A.: A linear-time solution for the Knapsack problem using active membranes, Lecture Notes in Computer Science, 2933 (2004), 140– 152. [11] P´erez-Jim´enez, M.J., Romero-Campero, F.J.: A CLIPS Simulator for Recognizer P Systems with Active Membranes, in this volume. [12] Riscos-N´u˜nez, A., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Towards a programming language in cellular computing, in this volume. [13] CLIPS Web Page: http:// www.ghg.net/clips/CLIPS.html [14] The P Systems Web Page: http://psytems.disco.unimib.it/ 430