The Spanning-tree Algorithm and Generating a Membrane Structure Šárka Vavrečková Silesian University in Opava, Bezručovo nám. 13, Opava, Czech Republic, sarka.vavreckova@fpf.slu.cz Abstract: Many articles on membrane systems seek to the current revision is IEEE 802.1D-2004, reaffirmed in minimize the number of membranes. But if these systems 2011 [2, 17]. were to be used for practical purposes, we may need a sys- The MST algorithm is one of the graph algorithms, and tem with a large number of membranes – the proper ar- it is one of the most known greedy algorithms. Greedy al- rangement of this structure would be very difficult. In this gorithms are heuristic problem-solving algorithms search- paper, we propose a procedure inspired by the spanning- ing for locally optimal choices with the intent to discover tree algorithm to help optimize a complex structure of a global optimum. More information is available at [6, 7]. membranes, independently of system rules. The paper [8] describes the implementation of Dijk- stra’s algorithm (finding the shortest path in a graph) using P system, which is closely related to the spanning-tree, but 1 Introduction a membrane system is a tool there, not a target. Membrane computing is a framework of parallel dis- A dynamic structure of membranes (P Systems with ac- tributed processing introduced by Gheorghe Pǎun in 1998. tive membranes) is discussed in [13] or [4], but the pre- Research in this area is ongoing and many different types sented structure was able to dissolve membranes and to of membrane systems have emerged since then. Informa- divide a membrane into two successor membranes. Each tion is available at [12, 14, 15, 16], or the bibliography at membrane has its polarization (electrical charge with val- [18]. ues {−, 0, +}), and the polarization of a membrane can The intent of Membrane computing is to abstract com- be changed as well. All changes of membranes are made puting using hierarchies of membranes in living cells. using rules. Since 2000, the term P Systems has been used for mathe- In this paper, we work with dynamics of membrane matical models of membrane systems. structure in a slightly different manner. Changes in the The minimum spanning tree (MST) for a given struc- membrane structure are not built in the rules of the mem- ture (network) of nodes is a substructure of the form of brane system, but they are meta-rules used to pre-prepare a tree with optimal paths leading from nodes to the root the structure of the system, which will then work accord- node, while maintaining the established rules for relation- ing to its own rules. ships between nodes, even when the structure is changed (adding new nodes, removing them or changing properties of connections). There are many applications of the MST 2 Analogy between Membrane Structure algorithm in various areas – network design, network op- and Tree Structure timization, maximum bottleneck paths, image processing, grouping objects into clusters of similar objects, approx- The basis of membrane systems is a membrane structure imation of some NP-hard problems (e.g. traveling sales- inspired by the structure of a biological cell. A membrane person problem), etc., see [1]. can contain certain objects and/or other (nested) mem- There are several algorithms to find the MST: Kruskal’s branes. Thus, there may be a parent-child relationship be- algorithm, Prim’s algorithm, Boruvka’s algoritm, the algo- tween the membranes. Objects can be manipulated using rithm in the STP protocol (Spanning-Tree Protocol). Some rules, in some membrane systems there are also rules for of them are discused in [3, 7]. manipulating membranes. We will deal with the algorithm implemented in STP, The membrane structure is strictly hierarchical, it can because, in addition to mathematical representation, it is be represented by a sequence of nested brackets or dis- well described in the form of code, although for the pur- played by a tree in which the parent-child relationship cor- poses of computer networks, and standardized. The MST responds to the inner-outer membrane relationship. One algorithm implemented in the STP protocol maintains a membrane (the skin) is the main one (it contains all loop-free logical topology with network devices (Ethernet the others), the remaining membranes always have one switches or bridges), keeping backup physical connections parental membrane in which they are contained. Analo- that are immediately available in the event of a change in gously, the tree has one main (root) node, all other nodes logical topology. STP was standardized as IEEE 802.1D, have exactly one parent node. The representation using a Copyright ©2020 for this paper by its authors. Use permitted under tree intuitively leads to the possibility of using graph algo- Creative Commons License Attribution 4.0 International (CC BY 4.0). rithms designed for graphs in the form of a tree. '' $ $ 1 ' $ is to receive a data unit called a frame from one port and 2 ' $ 5 3 forward it to another port, behind which the target device for the given frame is located. & % In general, we find it useful when there are redundant & % ' ' $ paths in a network. But if we create redundant paths in ' $ 6 $ 4 7 the network of switches, we also create loops, which have a negative impact on network operation (broadcast frames intended for all nodes in the network flow by the network & % & % & & % & %%in multiple copies, we call it “broadcast storm” ). The 1 solution is to leave redundant paths at the physical level Figure 1: Example of Membrane Structure (cables), but remove them at the logical level (communica- tion) by blocking data communication on a given connec- tion. In case that the active path stops to forward frames, The membrane structure can be represented graphically one of the logicaly blocked paths whose physical connec- using Venn diagrams, brackets, or a tree of nodes repre- tion exists will be activated. senting membranes. The membrane structure presented In the case of switches, the entire process is directed by in Figure 1 by Venn diagram is represented by the string the STP protocol, which implements the spanning-tree al- [ [ [ ]3 [ ]4 ]2 [ ]5 [ [ ]7 ]6 ]1 , and by the tree of nodes shown gorithm. The purpose of this algorithm is to negotiate its in Figure 2. position in the hierarchy when connecting the switch to 1 t @ the network and to keep the hierarchy in optimal condi- @ tion according to the general rules and set priorities when 2 t 5 t @t6 changing the network structure. Each node has assigned @ @ its own priority (in a parent-child relationship, the parent 3 t @t4 t7 will have a smaller priority number). The algorithm does not depend on the number of nodes, it runs in parallel at Figure 2: Tree of nodes all nodes and affects the structure of the entire network at the same time. The membranes are identified by their labels. The mem- When designing a large membrane structure, for each brane structure presented in Figures 1 and 2 uses simple membrane we usually have an idea of how deep in the numbers as labels. structure it should be roughly, and also which membranes There are many articles and procedures that deal with are considered parental for it. We want to choose one of the rules and objects in the membrane structure, but the the potential parents for the given membrane in the opti- membranes themselves are supposed to be “somehow mization process as the parent membrane, and thus actu- designed”, their structure is not usually specifically ad- ally include the given membrane into the structure (both dressed. It is not necessary for a few membranes; however, the membrane and the tree structure). We can solve the if this structure is to be large and very complex (which can choice of the main membrane or the root node of the tree happen, for example, in a structure for simulating the oper- for the whole system similarly. ation of many mutually hierarchically arranged systems), we may encounter problems in the design of such a struc- 3 Preliminaries ture. In the case of a complicated structure, it may happen that we do not correctly express suitable relationships be- 3.1 Membrane Structure and P Systems tween membranes, analogously in the tree we do not cor- rectly express parent-child relationships between nodes. We assume the reader to be familiar with the basics of the A tool we use for the design of a membrane structure formal language theory and membrane computing. For can allow input in the form of nested brackets or in graph- further details we refer to [10] and [16]. ical form. In brackets, we can get lost in small tens of The definition of P Systems follows, but only some parts membranes, the graphic input is lucid only till a certain ex- of the definition are important for the purposes of this ar- tent of the network: with tens to hundreds of membranes, ticle. Different types of P Systems have quite different we can get lost here as well. Or defining parenthood in definitions, and the mechanism we present is applicable to membranes can be manually challenging for larger struc- various types. tures. Each membrane has its region: the space delimited by In this paper, we propose an optimization process that the given membrane, all contained objects and subordinate can help organize a very large membrane structure. The membranes (with their contained objects) are situated in process remains laborious, but increases the probability of this region. The region of a membrane corresponds to the obtaining a better optimized structure. subtree in the tree representation of the structure. In local computer networks (LAN) we work with net- 1 The definition of broadcast storm can be found e.g. at https:// work devices of the type switch. The role of the switch www.techopedia.com/definition/6270/broadcast-storm. Definition 1 ([15]). Let H be a set of labels. A P System BID can be represented by the vector of a degree m, m ≥ 1, is a construct (priority ; deviceID) or by concatenation of these numbers (i.e. a number), Π = (V, T,C, µ, w1 , . . . , wm , (R1 , ρ1 ), . . . , (Rm , ρm )) the priority is more significant item than deviceID, where: • rootID is BID of the root node, so every node knows (i) V is a nonempty alphabet, its elements are called ob- the root, jects, • root path cost (sum of costs of all links on the way to (ii) T is an output alphabet, T ⊆ V , the root), (iii) C is a set of catalysts, C ⊆ V − T , • each port linked to a neighbor has its portID con- sisting of two parts: port priority and port number (iv) µ is a membrane structure consisting of m mem- (counted from 1), these two properties can be repre- branes, the membranes are labeled by the elements sented by a vector or concatenation similarly to BID, of H, • each port has three additional features: role, current (v) wi , 1 ≤ i ≤ m, are strings representing multisets over status, and cost of link. V associated with the region of the i − th membrane in µ, The port status is either forwarding (active) or blocking (the full algorithm defines more than two port states, also (vi) Ri , 1 ≤ i ≤ m, are finite sets of evolution rules asso- depending on the protocol version). ciated with the region of the i − th membrane in µ; The port role is one of the following: an evolution rule is a pair (u, v), also written u → v, where • root port – the active port through which the path to the root node leads (leading to the parent node), • u is a string over V , • v = v0 or v = v0 δ , where v0 is a string over • designated port – the active port leading to one of the ahere , aout , ain j a ∈ V, 1 ≤ j ≤ m , and δ is a child nodes (or leading to another subtree, blocked by special symbol ∈ / V representing dissolution of the neighbor), membrane, • alternate port – non-active (blocked) port. (vii) ρi , 1 ≤ i ≤ m, is a partial order relation over Ri spec- The original algorithm distinguishes two types of blocked ifying the priorities of the rules in Ri . ports (alternate or backup). Details and examples can be found in [15]. Algorithm 1: Basic Structures and Functions 3.2 The Spanning-tree Algorithm node : BID (priority, label), rootID (priority, label), For the purposes of this article, we will simplify the orig- RPcost, inal spanning-tree algorithm and list only those parts of it rootPortID, // portID of the root port that we will use for operations with a membrane structure. // ports are indexed by portID: The full algorithm can be found in [9] (multiple pages) and ports[] (role, state, cost, certainly [2]. The presented algorithms are created loosely neighborBID, neighborPortID); according to [9, 2, 5]. function node.init() As mentioned above, the spanning-tree algorithm is the begin parallel algorithm working on nodes of a network, e.g. on // Neighbors’ BIDs and their portIDs are interconnected network switches. The goal is to transform determined later from obtained BPDUs. the network into a tree with one root node. The process of // Setting port costs,... transformation is called convergence. self.IAmNewRoot(); // Defined in Algorithm 2. The algorithm was originally intended for network de- end vices called bridge, so the term “bridge” also appears in the following text. // No BPDU came from the neighbor for a hold Assume a network of nodes (bridges, switches, mem- time: the link or the neighbor is inoperative. branes,. . . ), interconnected in some manner. There can function node.noRespFromNeigh(recPortID) be more than one path between some nodes, the structure begin does not yet have the form of a tree, the convergence pro- if (recPortID = = self.rootPortID) then cess is in progress. // The root port waiting in vain for a BPDU. Every node keeps the following information: The root has become unavailable, maybe • BID (Bridge ID) consisting of two parts: I am the new root. self.IAmNewRoot(); – priority of the node, end – unique deviceID, e.g. MAC address of a switch, The port cost (or link cost, it should be the same value Algorithm 2: Auxiliary functions on the both sides of the link) is used to calculate the opti- mal path over network. The faster the port/link, the lower function node.changeRootPort(newRootPortID, this number (and better link). newPortRole) begin The representation of a node and its initialization can be // rootPortID==0 would mean that I am the root found in Algorithm 1. if (self.rootPortID != 0) then The nodes communicate with each other using BPDU self.ports[self.rootPortID].state = blocking; messages (Bridge Protocol Data Unit). BPDU is valid self.ports[self.rootPortID].role = only for one link and the corresponding ports, between newPortRole; two neighbors; it is not resent to another link, the neigh- bor generates the own BPDUs for its links. Every BPDU end contains, inter alia, the following information: self.rootPortID = newRootPortID; self.ports[newRootPortID].state = blocking; • BID of the sender, self.ports[newRootPortID].role = rootPort; • rootID (BID of the node that is being considered root end by the sender), // Obtained info about new root or root path cost • root path cost (cost of the path from the sender to the changed, do synchronization downwards. root), function node.makeSync(sender) • portID and cost of the port the BPDU is sent over, begin • other information. // Only connected/used ports are processed: foreach (port in self.ports) do The neighbors know each other through the BPDUs, in- port.state = blocking; cluding BIDs and portIDs, and the root path cost is calcu- self.ports[self.rootPortID].state = forwarding; lated by adding the cost of the link to the root path cost self.ports[self.rootPortID].sendBPDU_agree(); info obtained from the neighbor. foreach (port in self.ports) do There are several types of BPDUs: Proposal BPDU is if ((port.role = = designatedPort) sent downwards to inform its child nodes about the root or (port.role = = alternatePort)) then node, Agreement BPDU is sent upwards to agree with the port.sendBPDU_proposal() ; proposed root setting (see Algorithm 4), and others which end are not necessary for our purposes. The BPDUs are also used as a keep-alive mechanism function node.IAmNewRoot() between neighbor nodes and the neighbors inform each begin other about their parameters (BIDs, port numbers, etc.). self.rootID = self.BID; Presume a situation where a new node is added to the self.RPcost = 0; network. This node first assumes that it is the root, and self.rootPortID = 0; starts sending BPDUs with BID = rootID. All its ports have foreach (port in self.ports) do the role DP (designated port). Its neighbors receive the port.role = designatedPort; BPDU with this information and compare the reported port.state = blocking; rootID with the stored value. There are two possibilities: port.sendBPDU_proposal(); end 1. the reported rootID is greater than the stored rootID end – the new node does not become the root, 2. the reported rootID is less than the stored rootID – the new node becomes the root. The function node.IAmNewRoot() in Algorithm 2 illus- If a node obtains a BPDU with the declared rootID less trates this situation. (i.e. better) than its stored rootID, it updates the own struc- tures and sends the BPDUs to all neighbors (except of the Example 1. The numbers deviceID are usually MAC ad- original sender), so these neighbors learn the change, sub- dresses. For demonstration reasons, we will use only sequently their neighbors learn the change, etc. “small” numbers for the both priorities and deviceIDs. The root node has the root path cost = 0 for all its ports, If a node has the stored rootID = (32 ; 56) and an- so the newly connected node (considering to be root) sends other node is reporting rootID = (31 ; 82), the reported BPDUs with this value to its neighbors. Each receiving node becomes the new root (the lower number of prior- neighbor adds the cost of the receiving port/link to the ob- ity means precedence). But if another node later reports tained root path cost information (the first command of the rootID = (31 ; 95), the reported node will not become the function node.getBPDU_proposal() in Algorithm 3). The root (its priority is the same as the root priority, but its next step depends on which port the BPDU came over. The deviceID is greater, which means no precedence). first part of Algorithm 3 (the first “if” command block) il- Algorithm 3: Getting BPDU: Proposal // BPDU of the type “Proposal” received on the port “recPortID” from the given “sender” node. function node.getBPDU_proposal(recPortID, sender) begin refRPcost = sender.RPcost + self.ports[recPortID].cost; // Root path cost from sender + cost between us self.ports[recPortID].neighborBID = sender.BID; // Discovering neighbor’s BID self.ports[redPortID].neighborPortID = sender.portID; if (self.ports[recPortID].role = = rootPort) then // Info originated from the root port is trusted. if ((sender.rootID < self.rootID) or ((sender.rootID = = self.rootID) and (refRPcost != self.RPcost))) then // Path to the root has changed, but the direction remains. self.ports[self.rootPortID].state = blocking; // blocking before any change of ports self.rootID = sender.rootID; self.RPcost = refRPcost; self.makeSync(sender); // including sending BPDU Agreement upwards and Proposal downwards else if (sender.rootID > self.BID) then // The root has become unavailable, maybe I am the new root. self.IAmNewRoot() return; end if (sender.rootID < self.rootID) then // New root notified, the reported rootID is better than I know: self.changeRootPort(recPortID, designatedPort); // The receiving port becomes my new root port. self.rootID = sender.rootID; self.RPcost = refRPcost; self.makeSync(sender); else if (sender.rootID = = self.rootID) then // The same root, maybe some other change – root path cost or direction? if (refRPcost < self.RPcost) then // The root path cost has changed to a better value: changeRootPort(recPortID, designatedPort); self.RPcost = refRPcost; self.makeSync(sender); else if (refRPcost > self.RPcost) then // The root path cost has changed to a worse value: if (sender.BID > self.BID) then // The sender is either under me or inside another subtree self.ports[recPortID].role = designatedPort; // previously could have been alternatePort self.makeSync(sender); else // means: (sender.BID < self.BID), the sender is above me or inside another subtree self.ports[recPortID].state = blocking; self.ports[recPortID].role = alternatePort; end else // The same root and root path cost, but from different direction, choosing more eligible parent: if (sender.BID > self.ports[rootPortID].neighborBID) then // The present parent is better, no change. self.makeSync(sender); else if ((sender.BID < self.ports[rootPortID].neighborBID) or ((sender.BID = = self.ports[rootPortID].neighborBID) and (self.ports[recPortID].neighborPortID < self.ports[rootPortID].neighborPortID))) then // The potential new parent has better BID, changing the root port: foreach (port in self.ports) do if (port.role = = alternatePort) then port.role = designatedPort ; self.changeRootPort(recPortID, alternatePort); foreach (port in self.ports) do if (port.role = = designatedPort) then port.state = blocking; port.sendBPDU_proposal(); end end end end end lustrates the case for the root port of the node, while the 4 Optimization of Membrane Structure next code represents the case for designated and alternate ports. The algorithm can be run over an existing graph from The node considers the reported rootID, root path cost which we want to create a tree, or individual elements and other parameters to decide the best direction to the root (membranes) can be added gradually. and the corresponding port roles. If the BPDU with the Consider a set of membranes, each of them has correct rootID and the same lowest root path cost comes • contained objects, properties, functions, rules, etc., to more than one port (and therefore it is not possible to according to the type of membrane system, select the root port according to the above procedure), the • its own identifier (label) and priority (i.e. BID); the lower sender BID decides. If the sending nodes have the priority is added as metainformation for the purposes same BID (e.g. when two or more parallel links lead be- of the algorithm, tween two nodes), the portIDs of the sender’s port and the • the identifier and priority of the root membrane (skin; neighbor’s port leading to current root are compared and i.e. rootID); it will probably be appropriate to deter- the port with the neighbor’s lower portID is selected as the mine the skin membrane in advance and assign it the root port. lowest BID number directly, The configured ports are in the blocking state during • ports to several possible neighbors in the membrane determining port roles. structure (potential parents and children) – links (re- The both the reported rootID and the root path cost to- lations) to them, for each port we need its portID, gether flood in all directions from the root node: first to the neighbor BID and the portID for the link on the its neighbors (they count the cost of the link leading to the neighbor’s side, each such link is evaluated by cost as root plus zero), then to their neighbors (the value increases metainformation. again, they add the cost of the link to the obtained value), etc. Each node gets the necessary information gradually, There may be left default values for added properties, or the topology may change several times during the conver- we can set them manually to impact the resulting structure. gence; when a node detects a root change, it communi- To make the procedure as illustrative as possible, we cates information about the new root to its ports (except use the representation of the membrane structure in the the root port) during the synchronization process (the func- form of a tree. The procedure described in Algorithms tion node.makeSync(sender), see Algorithm 2). 1, 2, 3, and 4, is intended for network devices (however, very simplified), but we can use this simplified version for Whenever there is a change in the structure, in the prior- membranes and just modify the terms. ities of nodes or ports, etc., this procedure starts again and Algorithm 5 is created by modifying Algorithm 1, the the whole network gradually converges. If a node finds out remaining algorithms can be modified in a similar way. about the change: The port priorities are not necessary (we need just port la- • it evaluates the change reported in the BPDU pro- bels as portIDs), because we do not assume multiple con- posal, nections between two membranes. • if the node agrees, it changes its configuration and sends back the BPDU agreement, Example 2. Let us demonstrate the above outlined pro- • it blocks the ports to other neighbors and sends them cedure. For the sake of clarity, the individual membranes the BPDU proposal. are created sequentially, but we would achieve the same result even if all membranes were created in parallel or In case that a neighbor agrees, it sends back the BPDU when the order was changed, only the convergence pro- agreement (the port leading to this neighbor is activated cess would pass in different timing. The following initial with the role “designated”). If it does not agree, it sends structure is given: back the own proposal in the BPDU proposal. 3t.1 .2 2t.1 .1 1t.3 .1 6t cost=15 .3 cost=10 .2 cost=8 .2 .2@ @ cost cost cost co Algorithm 4: Getting BPDU: Agreement st= @ =10 =12 =16 12 @ .2 .1 .2 // BPDU “Agreement” received on the port @t cost=8 t cost=10 t .1 “recPortID”, my proposal is accepted by the 4 .3 .2 5 .3 .1 7 neighbor function node.getBPDU_agree(recPortID) Figure 3: Initial structure for Example 2 begin self.ports[recPortID].role = designatedPort; There are 7 membranes with connections and link costs, self.ports[recPortID].state = forwarding; the ports are marked in a smaller font and with a point, e.g. end the membrane no. 3 has the ports 3.1 (leading to the mem- brane no. 2) and 3.2 (leading to the membrane no. 4). All Algorithm 5: Base for Membranes • the membrane no. 5 is created, connected to no. 1 and membrane: BID (priority, label), 4; considered to be the root (sending Proposal), but rootID (priority, label), RPcost, receives back the message from the neighbors with rootPortID, the lower rootID (sending back Agreement), the root ports[] (role, state, cost, is no. 1; the root path cost from no. 1 is better (0 + neighborBID, neighborPortID); 12), so the port 5.1 gets the role RP, the port 5.2 gets th role AP, the opposite port 4.3 gets the role DP, function membrane.create(BID, neighs[], costs[]) • the membrane no. 4 found an alternative path to the begin root (no. 1) through no. 5 with the same root path self.BID = BID; cost; but the neighbor no. 2 has better BID, so the int c = neighs.count; root port remains, if c > 0 then 1 t for (int i = 1; (i <= MaxPorts) and (i <= c); @ i++) do @ self.ports[i].neighborBID = neighs[i]; 2 t 5 t @t6 self.ports[i].cost = costs[i]; @ @ ... ; // according to implementation @ @ 3 t @t4 @t7 end self.IAmNewRoot(); Figure 4: Modified structure (tree) for Example 2 end • the membrane no. 6 is created, connected to no. 1, af- function membrane.noRespFromNeigh(recPortID) ter exchanging messages the root is no. 1, the port 6.1 begin gets the role RP, if (recPortID = = self.rootPortID) then self.IAmNewRoot(); • the membrane no. 7 is created, connected to no. 5 and end 6, after exchanging messages the root is no 1, the port 7.1 gets the role RP (the root path cost through no. 5 is better), the opposite port 5.3 gets the role DP, the port 7.2 gets the role AP and the opposite port 6.2 membranes have the same priority: only labels are used gets the role DP. to make decisions when comparing BIDs. This structure is not in the form of tree, so we apply the transformation. Example 3. Setting various membrane priorities and dif- Assume that the structure is formed gradually, for ex- ferent link costs causes the topology change. Let us take ample from lower labels till larger labels (but the order is the previsous example and set the priority of the membrane not important). The steps are as follows: no. 2 to 100, the others to 200, and change the cost of the link between membranes no. 6 and 7 to the value 8. • the membrane no. 1 is created, it is the root (the skin membrane), all its ports have the role DP, (200,3) (100,2) (200,1) (200,6) t.1 .2 t.1 .1 t.3 .1 t • the membrane no. 2 is created and connected to the cost=15 .3 cost=10 .2 cost=8 .2 .2@ membrane no. 1; considered to be the root (sending @ cost cost cost co Proposal), but receives the message from no. 1 with st= @ =10 =12 =8 12 the lower (i.e. better) rootID (so sending back Agree- @ .2 .1 .2 ment), the root is no. 1, the port gets the role RP, @t cost=8 t cost=10 t .1 .3 .2 .3 .1 • the membrane no. 3 is created, connected to no. 2; (200,4) (200,5) (200,7) considered to be the root (sending Propossal), but Figure 5: Initial structure for Example 3 receives back the message from no. 2 with the lower rootID (sending back Agreement), the root is no. 1, As we can see (Figure 6), the structure has changed the port 3.1 gets the role RP, quite a lot. • the membrane no. 4 is created, connected to no. 2 and 2 t no. 3; considered to be the root (sending Proposal), @ but receives back the message from no. 2 and 3 with @ the lower rootID (sending back Agreement), the root 3 t 4 t @t1 is no. 1; the root path cost through no. 2 is 10 + 10 = 20, through no. 3 is 10 + 15 + 12 = 37, so the port 4.2 5 t 6 t t7 gets the role RP, the port 4.1 gets the role AP (because sender.BID < self.BID), the port 3.1 of the membrane Figure 6: Modified structure (tree) for Example 3 no. 3 goes to the role DP, 5 Conclusions [7] Greenberg, H.J.: Greedy Algorithms for Minimum Span- ning Tree [online]. Univeristy of Colorado (1998), online The aim of this work is not to design a comprehensive tool available at http://glossary.computing.society. for simulation of P systems, there is not enough space for informs.org/notes/spanningtree.pdf (Accessed that. The goal is only to design a procedure for generating June 4, 2020) suitable input, e.g. for P-Lingua type languages[11]. [8] Guo, P., Quan, Ch., Ye, L.: UPSimulator: A general P sys- Membrane systems can be used to simulate complex tem simulator. Knowledge-Based Systems, vol. 170, 2019, (real) systems with many relations. Real systems are be- pp. 20–25. ISSN: 0950-7051. ing changed over time (not only by deleting existing mem- [9] Hewlett Packard Enterprise: Calculation process of the branes) and the proposed procedure offers a way of repre- STP algorithm [online]. HPE FlexNetwork LAN Switch- senting mutual relations that can be dynamically adapted. ing Configuration Guide (2017), online available at The two examples show the consequences for the https://techhub.hpe.com/eginfolib/networking/ change in the membrane structure caused by the interven- docs/switches/7500/5200-1938a_l2-lan_cg/ content/495503520.htm (Accessed June 11, 2020) tion in only two parameters – the priority of one membrane and the cost of one link (relation). [10] Hopcroft, J.E., and Ullman, J.D.: Introduction to Au- tomata Theory, Languages and Computation. Addison- There is only one problem left to solve: if there are sev- Wesley, 1979. eral potential child membranes before using the algorithm [11] P-Lingua, Main Page [online]. Online available at http:// and only some of them are selected by the algorithm, or www.p-lingua.org/wiki/index.php/Main_Page (Ac- the parent-child relationship may change, then some rules cessed August 11, 2020) ain j may lose relevance. This must be taken into account [12] Păun, Gh.: Computing with membranes. J. Comput. Syst. when designing evolution rules, or the presented algorithm Sci. 61(1), 108–143 (2000). Turku Center for Computer can be enriched with the possibility of dynamic adaption Science-TUCS report 208, November 1998. of this type of evolution rules; of course, if the side effects [13] Păun, Gh.: Computing with membranes – A Variant: P Sys- of this modification will be acceptable. tems with Polarized Membranes. Intern. J. of Foundations of Computer Science, vol. 11, issue 1 (2000), pp. 167–182. The work is supported by The Ministry of Educa- [14] Păun, Gh.: Membrane Computing: An Introduction. tion, Youth and Sports of the Czech Republic from the Springer, Heidelberg (2002). National Programme of Sustainability (NPU II) project [15] Păun, Gh., Rozenberg, G.: A Guide to Membrane Com- IT4Innovations excellence in science – LQ1602. puting. Theor. Comp. Science, vol. 287, issue 1, pp. 73–100 (2002). References [16] Păun, Gh., Rozenberg, A., Salomaa, A. (eds.): The Ox- ford Handbook of Membrane Computing. Oxford University [1] Applications of Minimum Spanning Tree Press, New York (2010). Problem [online]. Geeks for Geeks (2018). [17] US Patent “Using Spanning Tree Protocol (STP) to En- URL: https://www.geeksforgeeks.org/ hance Layer-2 Network Topology Maps”, patent number US applications-of-minimum-spanning-tree/ (Ac- 8,045,488 B2, 2011. Also available at https://patents. cessed August 14, 2020) google.com/patent/US8045488B2/en. (Accessed June [2] 802.1D-2004 – IEEE Standard for Local and metropolitan 4, 2020) area networks: Media Access Control (MAC) Bridges [on- [18] The P Systems Website: http://psystems.eu (Accessed line]. IEEE (2011). URL: https://ieeexplore.ieee. June 4, 2020) org/document/1309630 (Accessed June 4, 2020) [3] Bazlamaçcı, C.F., Hindi, K.S.: Minimum-weight span- ning tree algorithms: A survey and empirical study. Computers & Operations Researche, vol. 28, issue 8, ISSN 0305-0548, pp. 767–785 (2001), online avail- able at: http://www.sciencedirect.com/science/ article/pii/S0305054800000071 [4] Calude, C., Păun, Gh.: Computing with Cells and Atoms. Taylor and Francis, London, 2000 (Chapter 3: “Computing with Membranes”). [5] ComputerNetworkingNotes: STP – Spanning Tree Pro- tocol Explained With Examples [online]. Networking Tutorials (2020). Online available at https://www. computernetworkingnotes.com/ccna-study-guide/ stp-spanning-tree-protocol-explained-with-examples. html (Accessed June 4, 2020) [6] Curtis, S.A.: The classification of greedy algorithms. El- sevier, 2003. Also available at https://core.ac.uk/ download/pdf/82042073.pdf (Accessed June 4, 2020)