Some Mathematical Methods and Tools for an Analysis of Harmony-Seeking Computations

Some Mathematical Methods and Tools for an Analysis of Harmony-Seeking Computations Adam Obtu lowicz Institute of Mathematics, Polish Academy of Sciences ´ Sniadeckich 8, P.O.B. 21, 00-956 Warsaw, Poland [email protected] Summary. A general review of some topic concepts and methods of membrane computing [15], [19] which can be useful in an analysis of harmony-seeking computations [1] is presented. Then an application of a certain particular method of membrane computing in a discussion of mobility of some systems considered in city planning [2] is described in some details. A conclusion of the discussion states that systems of hierarchical organization in a form of a tree are mobile by means of massively parallel (local) moves of the parts of the systems, where the moves are related to the process capabilities of moves of ambients in [7]. 1 Introduction An idea of a harmony-seeking computation was introduced and discussed in [1] aiming, among others, to improve design and planning in architecture in order to achieve that internal coherence (harmony) between the designed and planned objects of various scales (from the rooms in buildings, through buildings themselves, the districts of cities, and to cities themselves) which natural living system possesses. Therefore the discussion of harmony-seeking computations in [1] expands far beyond the methods of design and planning in architecture and concerns also better understanding of the phenomena of life with a regard to a geometric adaptation. The paper [1] contains general postulates for mathematical modeling of harmony-seeking computations. The aim of the present paper is to propose and review some known mathematical methods and tools which may serve for modeling harmony-seeking computations according to those postulates. The methods focus on modeling those evolution processes of natural (living) systems which may realize massively parallel computations themselves or inspire a planning of devices realizing these computations, where an aspect of geometric 248 A. Obtu lowicz adaptation is respected (on topological level) by considering certain possible transformations of hierarchical organization of systems during their evolution processes. A hierarchical organization is meant here as determined by a nesting relation of the less complex parts of a system in the more complex parts of a system. The proposed and reviewed in the paper (Section 2) mathematical methods and tools are mainly those already applied in membrane computing, a branch of natural computing initiated by Gh. P˘aun and described in [19] (see also the P systems page [15]), where the underlying structure of a system (called a membrane system) with respect to nesting of subsystems or its parts is a tree and this underlying structure may be transformed during an evolution process. In Section 3 and Appendix we present in some details a concrete application of membrane computing methods for an analysis of mobility (with respect to massively parallel moves) of certain systems considered in city planning and discussed in [2]. Section 3 together with Appendix are self-contained. The author thanks Krzysztof Wodiczko for long discussions about architecture and mathematics. 2 Membrane Systems and Their Evolution Rules; A General Review In [1] a harmony-seeking computation is identified with its underlying process whose steps are wholeness-extending-transformations (briefly W-E-transformations), where each W-E-transformation operates on one wholeness to produce another wholeness which is illustrated as follows: W1−W E1→W2−W E2→W3−W E3→W4−W E4→. . . . The character of W-E-transformations is established in [1] by five postulates A1–A5 about the structure of wholeness and three postulates B1–B3 about the definition of W-E-transformations themselves. In Postulate A5 each wholeness is identified (defined as) with a system of configurations, where according to Postulate A2 the subconfigurations may be spatially nested, or overlapping, or disjoint. One can see that membrane systems, the basic tools of membrane computing, meant as finite trees with nodes labeled by multisets are appropriate candidates to model (the structure of configurations identified with) a wholeness because the trees (and their Venn diagram presentation, cf. [19]) well describe the spatial nesting. Moreover, the description of evolution processes of membrane systems by using evolution rules in membrane computing also well suits to model the harmony-seeking computations. Namely, the evolution rules of membrane systems are similar to production rules generating languages and they can be simultaneously applied to membrane systems in a similar way like production rules for L-systems can be simultaneously applied to the processed expressions. We point out here Methods and Tools for an Analysis of Harmony-Seeking Computations 249 that a simulation of harmony-seeking process of tree growth by using a contextfree L-system is discussed in [1]. The known applications of membrane systems and their evolution rules for modeling processes in system biology presented among others in the recent papers contained in (Pre-)Proceedings of Workshops and Brainstorming Weeks on Membrane Computing (cf. [13], [14], [11], see the papers by D. Bezzossi, N. Busi and C. Zandron, L. Cardelli and Gh. P˘aun, V. Manca) show that it is worth to apply membrane computing methods and tools to model harmony-seeking computations. The most remarkable are those applications which concern fractals generation by P systems presented in [12], because fractals represent geometry of dynamic systems with a regard to similarities in various scales which is an important aspect of fractals applications in architecture, see [20]. 3 Semilattices of Subsets, Trees of Subsets, hereditarily finite sets, and Their Mobility The paper [2] contains a discussion of a thesis that a city structure of a form of a semilattice of subsets is better (topologically) adapted or more fit to live in than a structure of a form of a tree of subsets. In this section we introduce a representation of those semilattices and trees by certain hereditarily finite sets and then we show that this representation makes possible to transfer from [18] some results concerning mobile ambients and mobile membranes into the area of trees and semilattices of subsets and then into the realm of city planning. We quote from [2] the definitions of semilattices and trees of subsets. The semilattice axiom goes like this: A collection of sets forms a semilattice if and only if, when two overlapping sets belong to the collection, the set of elements common to both also belongs to the collection. The tree axiom states: A collection of sets forms a tree if and only if, for any two sets that belong to the collection, either one is wholly contained in the other, or else they are wholly disjoint. We use the following notion which is a generalization of the above defined concepts. We define a [finite]nesting structure to be an ordered pair N= (UN,NN) such that UNis a [finite] set, called the underlying set of N, and NNis a collection of nonempty subsets of UNwith UNbelonging to NN. The elements of NNare called the parts in N. For two parts n,n0in a nesting structure Nwe define that nis an immediate part of n0in N(and write n≺n0) if n(n0and for every part min Nif n⊆m⊆n0, then m=nor m=n0. We recall now the notion of a hereditarily finite set used in [18]. For a potentially infinite set Lof labels or names which are urelements, i.e., they are not (treated as) sets themselves, we define inductively a family of sets 250 A. Obtu lowicz HFifor natural numbers i≥0 such that HF0=∅, HFi+1 = the set of nonempty finite subsets of L∪HFi. The elements of the union HF = S{HFi|i≥0}∪{∅}are called hereditarily finite sets over Lor hereditarily finite sets with urelements in L, or simply hereditarily finite sets if there is no risk of confusion. For x∈HF we define its weak transitive closure WTC(x) and support supp(x) by WTC(x) = [WTC(y)|y∈xand y∈HF∪ {x} supp(x) = (x∩L)∪[{supp(y)|y∈xand y∈HF}, and the depth of xis defined to be the smallest natural number ifor which x∈HFi. The notion of a hereditarily finite set is applied in [10] to give a general characterization of physical computing devices. The characterization is improved in [4], [21], [22], and examples are given in [9]. Membrane computing applications of hereditarily finite sets are discussed in [16], [17], [18]. For a finite nesting structure N= (UN,NN) we define its hereditarily finite set hfs(N) by hfs(N) = UN−[{n∈ NN|n≺UN}∪ {hfs(N(n))|n∈ NNand n≺UN}, where for a part n∈ NNwe write N(n) to denote a nesting structure whose underlying set UN(n)is nitself and the set NN(n)of parts in N(n) is the set {n0∈ NN|n0⊆n}. For a hereditarily finite set xwe define its nesting structure Nxby UNx= supp(x),NNx={supp(y)|y∈WTC(x)}. A characterization of hereditarily finite sets of finite nesting structures is formulated in the following theorem which one can treat as a representation theorem of nesting structures by hereditarily finite sets. Theorem 1. For every finite nesting structure N, if xis the hereditarily finite set of N, i.e. x= hfs(N), then the following conditions hold: 0) Nx=N, 1) supp(y) = supp(y0)implies y=y0for all y, y0with {y, y0} ⊆ WTC(x), 2) y∈y0if and only if supp(y)≺supp(y0)for all y, y0with {y, y0} ⊆ WTC(x), 3) y∩S{supp(y0)|y0∈y}=∅for every y∈WTC(x). For every hereditarily finite set x, if it satisfies the conditions 1)–3), then hfs(Nx) = x. Methods and Tools for an Analysis of Harmony-Seeking Computations 251 Proof. One proves by induction on the number of elements of NNthat x= hfs(N) implies that the conditions 0)–3) hold for x. One proves by induction on the depth of xthat if the conditions 1)–3) hold for x, then hfs(Nx) = x. Corollary 1. For a finite nesting structure Nthe set WTC(hfs(N)) ordered by the membership relation ∈forms a structure which is isomorphic to that structure which is given by the set NNof parts in Nordered by ≺. Proof. The corollary is a consequence of Theorem 1. By 1) a mapping from WTC(hfs(N)) into NNgiven by y7→ supp(y) is a bijection which preserves the ordering by 2), where 1) and 2) are the conditions from Theorem 1 which hold for x= hfs(N). Example 1. The set xof the form (n1,2,{3}o,n2,{3},{3},{4}o, n{3},{4},5,{4}o,6,n{3},{4},5,{4}o) is a hereditarily finite set such that hfs(Nx) = x, where Nxis a semilattice illustrated in Fig. 0. • • ••• • • • • • • {3} {4} {2,3}{3,4}{4,5} {1,2,3}{2,3,4}{3,4,5} {1,2,3,4,5} {3,4,5,6} {1,2,3,4,5,6} Fig. 0. 252 A. Obtu lowicz The representation of finite nesting structures by hereditarily finite sets described in Theorem 1 and Corollary 1 provides that already defined constructions and proved properties of hereditarily finite sets xsatisfying hfs(Nx) = xcan be transferred or interpreted in the class of finite nesting structures. In particular, the basic concepts and constructions describing mobile systems1modeled by hereditarily finite sets, see [18] and Appendix in the present paper, can be transferred to the class of finite nesting structures via the representation. The following theorem is a starting point of this transfer. Theorem 2. Let xbe a hereditarily finite set such that hfs(Nx) = x. Then the following conditions hold: C1)if y∈xwith y∈HF, then for u1= (x− {y})∪ythe condition NNu1= NNx− {supp(y)}holds, C2)if {y, z} ⊆ x∩HF with y6=z, then for u2= (x− {y, z})∪ {z∪ {y}} the condition NNu2= (NNx− {supp(y)})∪ {supp(y)∪supp(z)}holds, C3)if z∈y∈xwith z∈HF, then for u3= (x− {y})∪ {y− {z}, z}the condition NNu3= (NNx− {supp(y)})∪ {supp(y− {z})}holds. Moreover, if Nxis such that NNxis a tree, then for every i∈ {1,2,3}the set NNuiis also a tree and hfs(Nui) = ui. Proof. We prove the theorem by induction on the depth of x. We interpret Theorem 2 in the following way. The conditions C1), C2), C3) correspond to the following process capabilities discussed in [7]: •condition C1) corresponds to the capability “can open an ambient”, •condition C2) corresponds to the capability “can enter an ambient”, •condition C3) corresponds to the capability “can exit out an ambient”. The above capabilities are capabilities of some “spatial” moves of parts of systems with respect to hierarchical organization of systems determined by nesting relation of parts. A mathematical description of the mentioned capabilities for systems modeled by hereditarily finite sets x(with WTC(x) meant as a collection of parts of x) is contained in conditions C1), C2), C3), where for every i∈ {1,2,3}the conditions written between “if” and “then” in Ci) are (pre)conditions which provide a realization of a move and the equation defining uiwritten after “then” in Ci) is a (post)condition describing the result uiof the move. For a hereditarily finite set xmodeling a system with parts represented by elements of WTC(x) the capabilities of moves can be applied (or referred) to the elements of WTC(x) and these applications are called local moves in x. The local moves are described in terms of Gh. P˘aun’s evolution rules and their applications in [18], see also Appendix of the present paper, where a local action is a mathematical description of a local move. 1Related to mobile ambient systems in [7]. Methods and Tools for an Analysis of Harmony-Seeking Computations 253 A collisionless set of simultaneous local moves in a given x(more than one local move in a unit of time) is described in [18] and Appendix as a proper set of local actions over x. An inductive formula for assembly of a whole system from the results of local moves belonging to a collisionless set of simultaneous local moves in a hereditarily finite set xis given in [18], see also the inductive definition of Ap(A, x) in Appendix, where Ap(A, x) is the result of assembly for a proper set Aof local actions over x. Theorem 3 in Appendix is the final and concluding step of the discussed transfer of the basic concepts and constructions describing mobile systems modeled by hereditarily finite sets into the area of nesting structures. Remark. For xgiven in Example, y=n1,2,{3}o,n2,{3},{3},{4}o,n{3},{4},5,{4}o, and z=n2,{3},{3},{4}o we have that z∈y∈xwhich means that preconditions in C3) hold for these x, y, z. Then for u3= (x− {y})∪ {y− {z}, z}we have that Nu3=Nx(because supp(y− {z}) = supp(y) in this case) which means that capability “can exit out an ambient” does not lead to any real move leaving Nxunchanged. Conclusion By virtue of Theorem 2 and Theorem 3 in Appendix every finite nesting structure Nwith NNbeing a tree is mobile with respect to simultaneous (massively parallel) local moves determined by process capabilities “can open an ambient”, “can enter an ambient”, and “can exit out an ambient”. The case discussed in Remark shows that mobility of some nesting structures Nwith NNbeing a semilattice is problematic. Appendix We consider those evolutive transformations of hereditarily finite sets into hereditarily finite sets which are determined by evolution rules written in P˘aun’s manner as the parenthesis expressions, cf. [19]: R1) [ ] →(dissolution rule), R2) [ ][ ] →[[ ]] (in-rule), R3) [[ ]] →[ ][ ] (out-rule), The single applications from the top of the above rules to hereditarily finite sets are described in the following way: 254 A. Obtu lowicz •if y∈x∩HF, then the dissolution rule [ ] →can be applied to xand the result of its application is a new hereditarily finite set of the form (x− {y})∪y, •if {y, z} ⊆ x∩HF, and z6=y, then the in-rule [ ][ ] →[[ ]] can be applied to x and the result of its application is a new hereditarily finite set of the form (x− {y, z})∪ {z∪ {y}}, •if z∈y∈x∈HF, z∈HF, and y− {z} 6=∅, then the out-rule [[ ]] →[ ][ ] can be applied to xand the result of its application is a new hereditarily finite set of the form (x− {y})∪({y− {z}, z} − {∅}). The above described single applications of evolution rules R1), R2), R3) from the top determine evolutive transformations of hereditarily finite sets into new hereditarily finite sets from the top. One sees that these rules are related to process capabilities “can open an ambient”, “can enter an ambient”, “can exit out an ambient”, introduced in [6]. The evolution rules may describe forces in patterns, cf. [3]. We describe by using ∪,−, and {?}a more complicated case of evolutive transformations of hereditarily finite sets, where these transformations are determined by simultaneous applications of different rules to many different elements of WTC(x) for a hereditarily finite set xto be transformed. The evolutive transformations of hereditarily finite sets considered above can be “transferred” to nesting structures by using the construction of Nx(see Theorem 1 and Corollary 1) to define evolutive transformations of nesting structures themselves. We restrict our considerations to tree-like hereditarily finite sets which are defined to be such that hfs(Nx) = xand Nxis a tree. Let xbe a tree-like hereditarily finite set. By a local action over xwe mean an ordered pair a= (Pa, Ra), where Pais a bijection from dom(a) into scope(a) with scope(a)⊂WTC(x) and Rais an evolution rule such that a1) if Rais a dissolution rule [ ] →, then dom(a) = {0,1}and Pa(1) ∈Pa(0), a2) if Rais an in-rule [ ][ ] →[[ ]], then dom(a) = {0,1,2}and {Pa(1), P a(2)} ⊂ Pa(0), a3) if Rais an out-rule [[ ]] →[ ][ ], then dom(a) = {0,1,2}and Pa(2) ∈Pa(1) ∈ Pa(0). For a local action aover xthe bijection Pais meant as a place of application of the rule Ra, where it will be seen later than one can interpret scope(a) as the scope of the local transformation of xaccording to the rule Ra. Let Abe a set of local actions over x. For a set y∈WTC(x) and a set z⊆ywe write A(y−z) to denote the set of local actions aover y−zsuch that a∈ A or Pa(0) = y−zwith a∗= (Pa∗, Ra)∈ A for Pa∗: dom(a)→ (scope(a)− {y−z})∪ {y}with Pa∗(i) = Pa(i) for all i∈dom(a)− {0}. If z=∅, Methods and Tools for an Analysis of Harmony-Seeking Computations 255 then A(y−z) = Ayis simply the set of those local actions over ywhich belong to A. If z=y, then A(y−z) = A∅=∅. For a set Aof local actions over xwe adopt the following notation Aα={a∈ A|Rais an α-rule}for α∈ {in,out}, Adiss ={a∈ A|Rais a dissolution rule}. We define now a property of sets Aof local actions over tree-like hereditarily finite sets xsuch that if Ahas this property, then one can construct the result of transformation of xwith respect to Ain a consistent (unambiguous) way, where xis transformed according to simultaneous application of the rules Rain places Pa, respectively for all a∈ A. A set Aof local actions over xis called a proper set of local actions over x if for all local actions a,a0in Aif a6=a0, then scope(a)∩scope(a0) = ∅or the disjunction of the following conditions holds: (C1)Pa(0) = Pa0(0) and (scope(a)− {Pa(0)})∩(scope(a0)− {Pa0(0)}) = ∅, (C2) if {a,a0} ⊆ Adiss, then Pa(0) = Pa0(1), (C3) if {a,a0} ⊆ Ain, then Pa(1) = Pa0(1) or Pa0(0) ∈ {Pa(1), P a(2)}, (C4) if {a,a0} ⊆ Aout, then Pa(0) = Pa0(2) or {Pa(1), Pa(2)} ∩ {Pa0(0), Pa0(1)}={Pa(1)}, (C5) if a∈ Adiss and a0∈ Ain, then Pa(1) = Pa0(0) or Pa(0) ∈ {Pa0(1), Pa0(2)}, (C6) if a∈ Adiss and a0∈ Aout, then Pa(1) = Pa0(0) or {Pa(0), P a(1)} ∩ {Pa0(1), Pa0(2)}={Pa(0)}, (C7) if a∈ Ain and a0∈ Aout, then Pa(1) = Pa0(1) or Pa0(0) ∈ {Pa(1), P a(2)} or scope(a)∩ {Pa0(1), Pa0(2)}={Pa(0)}. We adopt the following conventions to explain and illustrate the notion of a proper set of local actions. For a tree-like non-empty hereditarily finite set xwhose content is not specified (or is not important for considerations) we illustrate xby a drawing given by a triangle below whose bottom vertex is labeled by x. •x .. For a tree-like non-empty hereditarily finite set xwhose content is not specified we illustrate one-element set {x}by a drawing given by a triangle with an arrow glued to the bottom vertex of the triangle as below 262 A. Obtu lowicz 21. W. Sieg: Computability Theory. Seminar Lectures, University of Bologna, November 2004, http://www.phil.cmu.edu/summerschool/2006/Sieg/computability theory.pdf. 22. W. Sieg: Calculations by man and machine: conceptual analysis. Lecture Notes in Logic, 15 (2002), 390–409.