Recognizing Membrane Structures with Tree Automata

Recognizing Membrane Structures with Tree Automata? Jos´e M. Sempere, Dami´an L´opez Departamento de Sistemas Inform´aticos y Computaci´on Universidad Polit´ecnica de Valencia 46071 Valencia, Spain E-mail: {jsempere,dlopez}@dsic.upv.es Summary. In this work we propose a new model of tree automata based on multisets of states and symbols linked to the finite control. This new model accepts a set of trees with symmetries between their internal nodes. We name this property as mirroring. We propose an application of these automata to solve a problem related to P systems such as recognizing identic membrane structures. 1 Introduction One of the main components of P systems is the membrane structure that they define. This structure evolves during the computation time due to the application of rules associated to the membranes. The membrane structure can be represented by a tree in which the internal nodes denote regions which have inner regions inside. So, the root of the tree is always associated to the skin membrane of the P system. The relation between regions and trees has been recently stressed by Freund et al. [6]. These authors have established that any recursively enumerable set of trees can be generated by a P system with active membranes and string objects. So, P systems can be viewed as tree generators. In this work we propose a model to accept the tree structures defined by P systems. Our model is an extension of classical tree automata [7] in which the states and symbols of the finite control form multisets. Multiset theory has been linked to parallel processing as shown in [2]. The use of multisets in the finite control of tree automata implies the definition of a multiset tree automaton model. This new model is able to process a set of trees which have some symmetry properties linked to the internal nodes. These symmetries appear during the representation of membrane structures of P systems. That is, the initial order given to the regions of any P system is somehow arbitrary. ?Work supported by the Spanish CICYT under contract TIC2003-09319-C03-02. 306 J.M. Sempere, D. L´opez The renaming of regions and rules in any P system does not change its behavior during the computation. So, we have an exponential number of names that we can give to any P system. This fact is what we try to study by introducing symmetries (mirrorings) in the membrane structure. The problem of representation that we have referred before opens a new definition of confluent P systems. We can define structural confluent P systems as those systems in which the uniqueness of acceptance/rejection configurations is only referred to the membrane structure that they define. This will be investigated in future works. Another aspect that we try to solve is related to editing configurations. Recently, Csuhaj-Varj´u et al. [4] have proposed editing distances between configurations of P systems. Here, we initiate the first step towards editing structural configuration of P systems. That is, we can restrict the editing distances by taking into account only membrane structures. The new model that we propose in this work will be useful to calculate such distances. Here we can take advantage of a previous work on editing distances between trees and tree automata [9]. The structure of this work is as follows. First we introduce basic definitions and notation about multisets, tree languages and automata and P systems. In section 3, we define the new model of multiset tree automata. We define the relation of mirroring between trees and we establish some results between tree automata, multiset tree automata and mirroring trees. In section 4, we apply the new model to solve the acceptance of membrane structures and the equivalence between them. Finally, we draw some conclusions and give some guidelines for future works. 2 Notation and Definitions In the sequel we will provide some concepts from formal language theory, membrane systems and multiset processing. We suggest the books [14], [11], and [2] as basic references. Multisets First, we will provide some definitions from multiset theory as exposed in [15]. Definition 2.1 Let D be a set. A multiset over D is a pair hD, fiwhere f:D−→ Nis a function. Definition 2.2 Suppose that A=hD, fiand B=hD, giare two multisets. The removal of multiset Bfrom A, denoted by AªB, is the multiset C=hD, hiwhere for all a∈D h(a) = max(f(a)−g(a),0). Definition 2.3 Let A=hD, fibe a multiset; we will say that Ais empty if for all a∈D,f(a) = 0. Recognizing Membrane Structures with Tree Automata 307 Definition 2.4 Let A=hD, fiand B=hD, gibe two multisets. Their sum, denoted by A⊕B, is the multiset C=hD, hi, where for all a∈D h(a) = f(a) + g(a). Definition 2.5 Let A=hD, fiand B=hD, gibe two multisets. We will say that A=Bif the multiset (AªB)⊕(BªA)is empty. We are specially interested in the class of multisets that we call bounded multisets. They are multisets that hold the property that the sum of all the elements is bounded by a constant n. Formally, we will denote by Mn(D) the set of all multisets hD, fisuch that Pa∈Df(a) = n. A concept that is quite useful to work with sets and multisets is the Parikh mappings. Formally, a Parikh mapping can be viewed as the application Ψ:D∗→ Nnwhere D={d1, d2,· · · , dn}. Given an element x∈D∗we define Ψ(x) = (#d1(x),· · · ,#dn(x)) where #dj(x) denotes the number of occurrences of djin x. Later, we will use tuples of symbols and states as strings and we will apply the Parikh mapping as defined above. Tree automata and tree languages Now, we introduce some concepts from tree languages and automata as exposed in [3, 7]. First, let a ranked alphabet be the association of an alphabet Vtogether with a finite relation rin V×N. We denote by Vnthe subset {σ∈V|(σ, n)∈r}. Given a ranked alphabet Vwith rin V×N, we define the maximum arity of the alphabet as maxarity(V) = max{n|(σ, n)∈r}. The set VT, of trees over V, is defined inductively as follows: a∈VTfor every a∈V0, σ(t1, . . . , tn)∈VTwhenever σ∈Vnand t1, . . . , tn∈VT, n > 0. Atree language over Vis defined as a subset of VT. Given the tuple l=<1,2, . . . , k > we denote the set of permutations of lby perm(l). Let t=σ(t1, . . . , tn) be a tree over VT; we denote the set of permutations of tat first level by perm1(t). Formally, perm1(t) = {σ(ti1, . . . , tin)|< i1, i2, . . . , in>∈perm(<1,2, . . . , n >)}. Let N∗be the set of finite strings of natural numbers, separated by dots, formed using the catenation as the composition rule and the empty word λas the identity. Let the prefix relation ≤in N∗be defined by the condition that u≤vif and only if u·w=vfor some w∈N∗(u, v ∈N∗). A finite subset Dof N∗is called a tree domain if: u≤vwhere v∈Dimplies u∈D, and u·i∈Dwhenever u·j∈D(1 ≤i≤j). Each tree domain Dcould be seen as an unlabelled tree whose nodes correspond to the elements of Dwhere the hierarchy relation is the prefix order. Thus, each 308 J.M. Sempere, D. L´opez tree tover Vcan be seen as an application t:D→V. The set Dis called the domain of the tree t, and denoted by dom(t). The elements of the tree domain dom(t) are called positions or nodes of the tree t. We denote by t(x) the label of a given node xin dom(t). Let the level of x∈dom(t) be |x|. Intuitively, the level of a node measures its distance from the root of the tree. Then, we can define the depth of a tree tas depth(t) = max{|x| | x∈dom(t)}. In the same way, for any tree t, we denote the size of the tree by |t|and the set of subtrees of t(denoted with Sub(t)) as follows: Sub(a) = {a}for all a∈V0, Sub(t) = {t} ∪ [ i=1,...,n Sub(ti) for t=σ(t1, . . . , tn) (n > 0). Definition 2.6 Afinite deterministic tree automaton is defined as a system A= (Q, V, δ, F ), where Qis a finite set of states, Vis a ranked alphabet, Q∩V=∅, F⊆Qis the set of final states, and δ=Si|Vi6=∅δiis a set of transitions defined as follows: δn: (Vn×(Q∪V0)n)→Q, n = 1, . . . , m, δ0(a) = a, ∀a∈V0. From now on, we will refer to finite deterministic tree automata simply as tree automata. We suggest [3, 7] for other definitions on tree automata. The transition function δis extended to a function δ:VT→Q∪V0on trees as follows: δ(a) = afor any a∈V0, δ(t) = δn(σ, δ(t1), . . . , δ(tn)) for t=σ(t1, . . . , tn) (n > 0). Note that the symbol δdenotes both the set of transition functions of the automaton and the extension of these functions to operate on trees. In addition, one can observe that the tree automaton Acannot accept any tree of depth zero. Given a finite set of trees T, let the subtree automaton for Tbe defined as ABT= (Q, V, δ, F), where: Q=Sub(T), F=T, δn(σ, u1, . . . , un) = σ(u1, . . . , un), σ(u1, . . . , un)∈Q, δ0(a) = a, a ∈V0. P systems Finally, we will introduce basic concepts from membrane systems taken from [11]. A general Psystem of degree mis a construct Recognizing Membrane Structures with Tree Automata 309 Π= (V, T, C, µ, w1,· · · , wm,(R1, ρ1),· · · ,(Rm, ρm), i0), where: •Vis an alphabet (the objects), •T⊆V(the output alphabet), •C⊆V,C∩T=∅(the catalysts), •µis a membrane structure consisting of mmembranes, •wi, 1 ≤i≤m, is a string representing a multiset over Vassociated with the region i, •Ri, 1 ≤i≤m, is a finite set of evolution rules over Vassociated with the ith region and ρiis a partial order relation over Rispecifying a priority. An evolution rule is a pair (u, v) (or u→v) where uis a string over Vand v=v0or v=v0δwhere v0is a string over {ahere, aout, ainj|a∈V, 1≤j≤m} and δis an special symbol not in V(it defines the membrane dissolving action). From now on, we will denote the set {here, out, ink|1≤k≤m}by tar. •i0is a number between 1 and mand it specifies the output membrane of Π(in the case that it equals to ∞the output is read outside the system). The language generated by Πin external mode (i0=∞) is denoted by L(Π) and it is defined as the set of strings that can be defined by collecting the objects that leave the system by arranging them in the leaving order (if several objects leave the system at the same time then permutations are allowed). The set of numbers that represent the objects in the output membrane i0will be denote by N(Π). Obviously, both sets L(Π) and N(Π) are defined only for halting computations. One of the multiple variations of P systems is related to the creation, division and modification of membrane structures. There have been several works in which these variants have been proposed (see, for example, [1, 10, 11, 12]). In the following, we enumerate some kind of rules which are able to modify the membrane structure: 1. 2-division: [ha]h→[h0b]h0[h00 c]h00 , 2. Creation: a→[hb]h, 3. Dissolving: [ha]h→b. The power of P systems with the previous operations and other ones (e.g. exocytosis, endocytosis, etc.) has been widely studied in the previously related works and other ones. 3 Multiset Tree Automata and Mirrored Trees We will extend over multisets some definitions of tree automata and tree languages. First, we will introduce the concept of multiset tree automata and then we will try to characterize the set of trees that it accepts. Observe that our approach is a 310 J.M. Sempere, D. L´opez little bit different from Csuhaj-Varj´u et al. [5] and from Kudlek et al. [8] where, the authors consider the case that bags of objects are analyzed by an abstract machine. Here, we do not consider bags of (sub)trees but we introduce bags of states and symbols in the finite control of the automata. Given any tree automata A= (Q, V, δ, F) and δn(σ, p1, p2, . . . , pn)∈δ, we can associate to δnthe multiset hQ∪V0, fi ∈ Mn(Q∪V0) where fis defined by Ψ(p1p2. . . pn). The multiset defined in this way will be denoted by MΨ(δn). Alternatively, we can define MΨ(δn) as MΨ(p1)⊕MΨ(p2)⊕ · · · ⊕ MΨ(pn), where for all 1 ≤i≤n,MΨ(pi)∈ M1(Q∪V0). Observe that if δn(σ, p1, p2, . . . , pn)∈δ, δ0 n(σ, p0 1, p0 2, . . . , p0 n)∈δ, and MΨ(δn) = MΨ(δ0 n), then δnand δ0 nare defined over the same set of states and symbols but in different order (that is the multiset induced by hp1, p2,· · · , pniequals to the one induced by hp0 1p0 2. . . p0 ni). Now, we can define a multiset tree automaton that performs a bottom-up parsing as in the tree automaton case. Definition 3.1 Amultiset tree automaton is defined by the tuple MA = (Q, V, δ, F), where Qis a finite set of states, Vis a ranked alphabet with maxarity(V) = n,Q∩V=∅,F⊆Qis a set of final states, and δis a set of transitions defined as follows: δ=[ 1≤i≤n i:Vi6=∅ δi, δi: (Vi× Mi(Q∪V0)) → P(M1(Q)), i = 1, . . . , n, δ0(a) = MΨ(a)∈ M1(Q∪V0),∀a∈V0. We can take notice that every tree automaton Adefines a multiset tree automaton MA as follows. Definition 3.2 Let A= (Q, V, δ, F)be a tree automaton. The multiset tree automaton induced by Ais defined by the tuple MA = (Q, V, δ0, F ), where each δ0is defined as follows: MΨ(r)∈δ0 n(σ, M)if δn(σ, p1, p2, . . . , pn) = rand MΨ(δn) = M. Observe that, in the general case, the multiset tree automaton induced by A is non-deterministic. As in the case of tree automata, δ0could also be extended to operate on trees. Here, the automaton analyzes the leaves of the tree first through δ0. Then, by making a bottom-up parsing, the tuples of states and/or symbols are transformed in multisets by using the Parikh mapping Ψto obtain the multisets in Mn(Q∪V0). If the analysis is completed and δ0returns a multiset with at least one final state, the input tree is accepted. So, δ0can be extended as follows Recognizing Membrane Structures with Tree Automata 311 δ0(a) = MΨ(a) for any a∈V0, δ0(t) = {M∈δ0 n(σ, M1⊕ · · · ⊕ Mn)|Mi∈δ0(ti)1 ≤i≤n}, for t=σ(t1, . . . , tn) (n > 0). Formally, every multiset tree automaton MA accepts the following language L(MA) = {t∈VT|MΨ(q)∈δ0(t), q ∈F}. Theorem 3.1 Let A= (Q, V, δ, F)be a tree automaton, MA = (Q, V, δ0, F )be the multiset tree automaton induced by A, and t=σ(t1, . . . , tn)∈VT. If δ(t) = q, then MΨ(q)∈δ0(t). Proof. We will proceed by induction on the depth of the tree. Base of induction: Let us consider that t=σ(a1, . . . , an) with ai∈V0and δn(σ, a1,··· , an) = q. The definition of δ0implies that MΨ(q)∈δ0(σ, MΨ(a1a2. . . an)) so MΨ(q)∈δ0(t). Induction hypothesis: Let us consider that depth(t)< n. If δ(t) = qthen MΨ(q)∈δ0(t). Induction step: depth(t) = n. Let us suppose that t=σ(t1,· · · , tn) with depth(ti)< n for 1≤i≤n. Our induction hypothesis establishes that, if δ(ti) = qi, then MΨ(qi)∈ δ0(ti) for 1 ≤i≤n, Then, δ0 n(σ, t1,··· , tn) = δ0 n(σ, P ) with P=MΨ(q1. . . qn)∈ Mn(Q∪V0). So, if δn(σ, q1,· · · , qn) = r, then the construction of δ0ensures that MΨ(r)∈δ0 n(σ, P ) = δ0(t). Corollary 3.1 Let A= (Q, V, δ, F)be a tree automaton and MA = (Q, V, δ0, F ) be the multiset tree automaton induced by A. If t∈L(A), then t∈L(MA). Mirrored equivalent trees We now introduce the concept of mirroring in tree structures. Informally speaking, two trees will be related by mirroring if some permutations at the structural level are mad. For example, the trees given in Figure 1 have identical subtrees except that some internal nodes have changed their order. We propose a definition that relates all the trees with this mirroring property. Definition 3.3 Let tand sbe two trees from VT. We say that tand sare mirror equivalent, denoted by t ./ s, if one of the following conditions holds: 1. t=s=a∈V0, 2. t∈perm1(s), 3. t=σ(t1, . . . , tn),s=σ(s1, . . . , sn)and there exists < s1, s2, . . . , sk>∈ perm(< s1, s2, . . . , sn>)such that ti./ sifor all 1≤i≤n. Property 3.1 ./ is a binary equivalence relation (i.e., it is reflexive, symmetric and transitive). 312 J.M. Sempere, D. L´opez ¡¡ ¡@@ @ G H D ¡¡¡@@@ E B ¡¡¡ ¡@@@ @ A C F ¡¡¡ ¡@@@ F D B ¡ ¡ ¡ @@ @ H G ¡¡¡ ¡@@@ @ A C F Fig. 1. Two mirrored trees. Theorem 3.2 Let A= (Q, V, δ, F)be a tree automaton, t=σ(t1, . . . , tn)∈VT, and s=σ(s1, . . . , sn)∈VT. Let MA = (Q, V, δ0, F )be the multiset tree automaton induced by A. If t ./ s, then δ0(t) = δ0(s). Proof. We will proceed by induction on the depth of the tree. Base of induction: Let us take tand swith depth(t) = depth(s) = 1. It is easy to see that the transition function δ0consider in the same way every permutation of the leaves of t, that is, every mirror equivalent tree to t. Induction hypothesis: Let us consider that depth(t) = depth(s)< n. If t ./ s, then δ0(t) = δ0(s). Induction step: Finally, take tand swith depth(t) = depth(s) = n. Let us suppose that t ./ s with t=σ(t1,··· , tn) and s=σ(s1,· · · , sn). Therefore, for each tithere exist sj such that ti./ sj, 1 ≤i, j ≤nand, due to our induction hypothesis, δ0(ti) = δ0(sj). So, the set of multisets defined by δ0(t1)⊕· · ·⊕δ0(tn) is equal to the set of multisets defined by δ0(s1)⊕ · · · ⊕ δ0(sn) and δ0(t) = δ0(s). Note that the reciprocal of last theorem is not generally true. For instance, consider the trees t=σ(a) and s=σ(a, σ(a)) and the tree automaton with the following transition function: δ1(σ, a) = q1∈F, δ2(σ, a, q1) = q1∈F. It is easy to see that δ0(t) = δ0(s) but tis not mirror equivalent to s. Corollary 3.2 Let A= (Q, V, δ, F )be a tree automaton, MA = (Q, V, δ0, F )the multiset tree automaton induced by Aand t∈VT. If t∈L(MA), then s∈L(MA) for any s∈VTsuch that t ./ s. Recognizing Membrane Structures with Tree Automata 313 Proof. Note that if t∈L(A) then t∈L(MA) due to Theorem 3.1 and Corollary 3.1. Finally, by Theorem 3.2, if t ./ s, then δ0(t) = δ0(s) and s∈L(MA). This result suggests an algorithm to determine whether two trees are mirror equivalent or not. The algorithm is shown in Figure 2 Input: Two trees t, s ∈VT Output: Answer to t ./ s Method: 1. Let ABt= (Q, V, δ, F) be the subtree automaton for the set {t} 2. Let MABt= (Q, V, δ0, F ) be the mirrored tree automaton induced by ABt 3. if (δ0(s)∩F6=∅) then return TRUE else return FALSE fi Fig. 2. Algorithm to determine if two trees are mirror equivalent. Note that given s, t ∈VT, the algorithm constructs ABtand MABt. By Corollary 3.1, t∈L(MABt) and, due to Corollary 3.2, if t ./ s, then s∈L(MABt). In addition, if tis not mirror equivalent to s, then δ0(s) is not defined due to the construction of ABtwhich is deterministic and accepts only t. Observe that the multiset tree automaton MABtcould be non-deterministic. For example, if δ(σ, a, b) = q1and δ(σ, b, a) = q2is defined for ABt, then δ0(σ, MΨ(ab)) = {MΨ(q1), MΨ(q2)}is defined for MABt. This case could be avoided: just rename the state q2as q1during the construction in step 2 of the proposed algorithm. So, we can assume that MABtis deterministic too. The subtree automaton ABtproposed in the algorithm contains neither loops nor cycles. It is possible to establish in polynomial time if MABtaccepts a given tree s. Furthermore, we will prove that the proposed algorithm runs in polynomial time with the size of the input tree t. Lemma 3.1 Algorithm of Figure 2 runs in time O(|t|2). Proof. First, the operations ⊕and the symmetric difference, defined over multisets, can be performed in time O(n) where nis the size of the set that defines the multiset [13]. In this case, n=|t|. Now we will analyze the time complexity of the algorithm step by step Step 1 runs in time O(|t|). Step 2 runs in time O(|t|2). Observe that the number of multiset operations involved in the construction of MABtis bounded by the size of the automaton ABtwhich is bounded by |t|.