On Two Families of Multiset Tree Automata

On Two Families of Multiset Tree Automata? Jos´e M. Sempere, Dami´an L´opez Departamento de Sistemas Inform´aticos y Computaci´on Universidad Polit´ecnica de Valencia {jsempere,dlopez}@dsic.upv.es Summary. The relation between the membrane structures of P systems and an extension of tree automata which introduces multisets in the transition function has been proposed in previous works. Here we propose two features of tree automata which have been previously studied (namely, reversibility and local testability) in order to extend them to multiset tree automata. The characterization of these families will introduce a new characterization of membrane structures defined by the set of rules used for membrane creation and deletion. 1 Introduction The relation between membrane structures and tree languages has been explored in previous works. So, Freund et al. [4] proved that P systems are able to generate recursively enumerable sets of trees through their membrane structures. Other works have focused on extending the definition of finite tree automata in order to take into account the membrane structures generated by P systems. So, in [13], the authors propose an extension of tree automata, namely multiset tree automata, in order to recognize membrane structures. In [7], the authors propose the use of this model to calculate editing distances between membrane structures. Later, the authors proposed a method to infer multiset tree automata from membrane observations [14]. In this work we introduce two new families of multiset tree automata, by using previous results taken from tree language theory. We propose a formal definition of reversible multiset tree automata and local testable multiset tree automata. These features have been widely studied in previous works [6, 8]. The structure of this work is simple: first we give basic definitions and notation for tree languages, P systems and multiset tree automata and we define the new families of multiset tree automata. Finally, we give some guidelines for future research. ?Work supported by the Spanish Generalitat Valenciana under contract GV06/068. 316 J.M. Sempere, D. L´opez 2 Notation and definitions In the sequel we will provide some concepts from formal language theory, membrane systems and multiset processing. We suggest the following books to the reader [12], [10] and [2]. 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. 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. The size of any multiset M, denoted by |M|will be the number of elements that it contains. 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. P systems We will introduce basic concepts from membrane systems taken from [10]. A general Psystem of degree mis a construct Π= (V, T, C, µ, w1,· · · , wm,(R1, ρ1),· · · ,(Rm, ρm), i0), where: •V is an alphabet (the objects) •T⊆V(the output alphabet) On Two Families of Multiset Tree Automata 317 •C⊆V,C∩T=∅(the catalysts) •µis a membrane structure consisting of mmembranes •wi, 1 ≤i≤mis a string representing a multiset over Vassociated with the region i •Ri, 1 ≤i≤mis 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 tar by {here, out, ink: 1 ≤k≤m}. •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 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, 9, 10, 11]). 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. Tree automata and tree languages Now, we will introduce some concepts from tree languages and automata as exposed in [3, 5]. 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}. The set VTof trees over V, is defined inductively as follows: a∈VTfor every a∈V0 σ(t1, ..., tn)∈VTwhenever σ∈Vnand t1, ..., tn∈VT, (n > 0) and let a tree language over Vbe defined as a subset of VT. 318 J.M. Sempere, D. L´opez Given the tuple l=<1,2, ..., k > we will denote the set of permutations of lby perm(l). Let t=σ(t1, ..., tn) be a tree over VT, we will 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 unlabeled tree whose nodes correspond to the elements of Dwhere the hierarchy relation is the prefix order. Thus, each 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) Given a tree t=σ(t1, . . . , tn), the root of twill be denoted as root(t) and defined as root(t) = σ. If t=athen root(t) = a. The successors of a tree t= σ(t1, . . . , tn) will be defined as Ht=< root(t1), . . . , root(tn)>. Finally, leaves(t) will denote the set of leaves of the tree t. Definition 2.6 Afinite deterministic tree automaton is defined by the tuple 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 Given the state q∈Q, we define the ancestors of the state q, denoted by Ant(q), as the set of strings On Two Families of Multiset Tree Automata 319 Ant(q) = {p1· · · pn:pi∈Q∪V0∧δn(σ, p1, ..., pn) = q} From now on, we will refer to finite deterministic tree automata simply as tree automata. We suggest [3, 5] 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, you 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 Let $ be a new symbol in V0, and VT $the set of trees (V∪ {$})Twhere each tree contains $ only once. We will name the node with label $ as link point when necessary. Given s∈VT $and t∈VT, the operation s#tis defined as: s#t(x) = s(x) if x∈dom(s), s(x)6= $ t(z) if x=yz, s(y) = $, y ∈dom(s) therefore, given t, s ∈VT, let the tree quotient (t−1s) be defined as: t−1s=r∈VT $:s=r#tif t∈VT−V0. tif t∈V0. this quotient can be extended to consider set of trees T⊆VTas: t−1T={t−1s:s∈T} For any k≥0, let the k-root of a tree tbe defined as follows: rootk(t) = t, if depth(t)< k t0:t0(x) = t(x), x ∈dom(t)∧ |x| ≤ k, otherwise 320 J.M. Sempere, D. L´opez Multiset tree automata and mirrored trees We will extend over multisets some definitions of tree automata and tree languages. We will introduce the concept of multiset tree automata and then we will characterize the set of trees that it accepts. 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 such way will be denoted by MΨ(δn). Alternatively, we can define MΨ(δn) as MΨ(p1)⊕MΨ(p2)⊕ · · · ⊕ MΨ(pn) where ∀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 2.7 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 2.8 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 carries out a bottom-up parsing where the tuples of states and/or symbols are transformed 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 On Two Families of Multiset Tree Automata 321 δ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} Another extension which will be useful is the one related to the ancestors of every state. So, we define AntΨ(q) = {M:MΨ(q)∈δn(σ, M)}. Theorem 2.9 (Sempere and L´opez, [13]) Let A= (Q, V, δ, F)be a tree automaton, MA = (Q, V, δ0, F)be the multiset tree automaton induced by Aand t=σ(t1, . . . , tn)∈VT. If δ(t) = qthen MΨ(q)∈δ0(t). Corolary 2.10 (Sempere and L´opez, [13]) 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). We will introduce the concept of mirroring in tree structures as exposed in [13]. Informally speaking, two trees will be related by mirroring if some permutations at the structural level are hold. We propose a definition that relates all the trees with this mirroring property. Definition 2.11 Let tand sbe two trees from VT. We will 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 ∀1≤i≤n ti./ si Theorem 2.12 (Sempere and L´opez, [13]) Let A= (Q, V, δ, F)be a tree automaton, t=σ(t1, . . . , tn)∈VTand 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). Corolary 2.13 (Sempere and L´opez, [13]) 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, for any s∈VTsuch that t ./ s,s∈L(MA). The last results were useful to propose an algorithm to determine whether two trees are mirror equivalent or not [13]. So, given two trees sand t, we can establish in time O((min{|t|,|s|})2) if t ./ s. 322 J.M. Sempere, D. L´opez 3k-testable in the strict sense (k-TSS) multiset tree languages and reversible multiset tree languages In the following section, we will define two new classes of multiset tree languages. The definitions related to multiset tree automata come from the relation between mirrored trees and multiset tree automata which we have established in the previous section. So, whenever we refer to multiset tree languages we are taking under our consideration the set of (mirrored) trees accepted by multiset tree automata. We refer [6] in order to know more about reversibility and local testability in tree languages. First, we define k-TSS tree languages for any k≥2. Definition 3.1 Let T⊆VTand the integer value k≥2.Tis a k-TSS multiset tree language if and only if, given whatever two trees u1, u2∈VTsuch that rootk−1(u1) = rootk−1(u2),u−1 1T6=∅and u−1 2T6=∅implies that u−1 1T=u−1 2T Any multiset tree automaton that holds the definition given before will be named a k-TSS multiset tree automaton. We can give the following characterization of such automata. Corolary 3.2 Let Abe a k-TSS multiset tree automaton. There not exist two distinct states q1, q2such that rootk(q1)∩rootk(q2)6=∅ Example 3.3 Consider the multiset tree automaton with transitions: δ(σ, aa)=q1 δ(σ, a)=q2 δ(σ, aq2)=q2 δ(σ, q1q1)=q1 δ(σ, aq2q1)=q3∈F Note that the multiset tree language accepted by the automaton is k-TSS for any k≥2. Note also that the following one does not hold the k-TSS condition for any k≥2: δ(σ, aa)=q1 δ(σ, bb)=q2 δ(σ, q2q2)=q2 δ(σ, q1q1)=q1 δ(σ, q2q1)=q3∈F because both the states q1and q2(and q3) share a common k-root.  We also extend a previous result concerning k-reversible tree languages (for any k≥0) to give the following definition. On Two Families of Multiset Tree Automata 323 Definition 3.4 Let T⊆VTand the integer value k≥0.Tis a k-reversible multiset tree language if and only if, given whatever two trees u1, u2∈VTsuch that rootk−1(u1) = rootk−1(u2), whenever there exists a context t∈VT $such that both u1#t, u1#t∈T, then u−1 1T=u−1 2T Example 3.5 Consider the multiset tree automaton with transitions: δ(σ, aa)=q1 δ(σ, a)=q2 δ(σ, q2q2)=q2 δ(σ, aaq1)=q1 δ(σ, q1q1)=q3∈F δ(σ, q2q1)=q3∈F the multiset tree language accepted by this automaton is k-reversible and it is also an example of non k-TSS multiset tree language.  Finally, we can relate the two families of multiset tree languages that we have previously defined with the following result. Theorem 3.6 Let T⊆VTand an integer value k≥2, if Tis k-TSS then Tis (k−1)-reversible. Proof. Let t#t1and t#t2belong to T, with t∈VT $and rootk(t1) = rootk(t2), trivially t−1 1T6=∅and t−1 2T6=∅. If Tis a k-TSS tree language, then by previous definitions, t−1 1T=t−1 2T, and also Tis (k−1)-reversible.  4 Conclusions and future work We have introduced two new families of multiset tree languages. Now, the open question is the characterization of membrane structures defined by them. We think that reversibility and local testability will introduce restrictions in the way of defining membrane creation and deletion. This will be explored in future works. References 1. A. Alhazov, T.O. Ishdorj: Membrane operations in P systems with active membranes. In Proc. Second Brainstorming Week on Membrane Computing. TR 01/04 of RGNC, Sevilla University, 2004, 37–44. 2. C. Calude, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: Multiset Processing. LNCS 2235, Springer, 2001.