Description

10 International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, 2010 REPRESENTIN TREE STRUCTURES BY NATURAL NUMBERS Caren Luengo, Luis Fernández, Fernando Arroyo Abstract: Transforation

Information

Category:
## Magazines/Newspapers

Publish on:

Views: 19 | Pages: 8

Extension: PDF | Download: 0

Share

Transcript

10 International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, 2010 REPRESENTIN TREE STRUCTURES BY NATURAL NUMBERS Caren Luengo, Luis Fernández, Fernando Arroyo Abstract: Transforation of data structures into natural nubers using the classical approach of gödelization process can be a very powerful tool in order to encode soe properties of data structures. This paper presents soe introductory ideas in order to study tree data structures under the pris of ödel nubers, and presents a few exaples of using this approach to trees. Keywords: Data structures, Trees, ödelization ACM Classification Keywords: E.1 Data Structures - Trees Introduction In [Luengo, 2008] was introduced a very interesting ethod in order to describe a Transition P syste as a natural nuber. The process is based on the classical and very well nown gödelization ethod. That paper described the way to find out the corresponding ödel nuber to a transition P systes. A very iportant part of the process is to represent the ebrane systes, a tree structure, as a natural nuber. In that paper the ebrane structure was represented in a very naïf way, which it has been deonstrated to be not enough in order to recover the tree structure fro the natural nuber that represents it. Following with this idea, in this paper it is depicted a setch for assigning natural nubers to tree structures, which perits recover the tree fro the natural nuber. Tree definitions A tree is an undirected siple graph T = (V, E) satisfying that it is connected and has no cycles. A tree T is said to be directed if it is a directed graph which would be a tree if directions on edges are not considered. A tree T is said to be rooted if one vertex is designed as root, in which case the edges have a natural orientation, towards or away fro the root. In rooted trees, the parent of a vertex is the vertex connected to it on the path to the root. Every vertex on the tree has a unique parent except for the root. A child of a vertex v is a vertex of which v is the parent. And finally, a leaf is a vertex without children. Rooted trees are the ey eleent to define tree data structure and, on this context, vertexes are usually denoted as node and edges are usually denoted as lins. In Mebrane Systes literature, a ebrane structure is defined by a language MS over the alphabet { [, ] }, as follows: 1. [ ] MS 2. if 1,, n MS for soe n 1, then [ 1,, n] MS Once the language is established, in order to properly define ebrane structure is needed to consider the following relation over the eleents of MS: 1 ~ 2 if and only if we can write the two strings in the for 1=μ 1μ 2μ 3μ 4, 2=μ 1μ 3μ 2μ 4, for μ 1 4 MS and μ 2, μ 3 MS. That is, if two neighbouring pairs of parentheses are International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, interchanged, together with their contents, then we obtain the sae ebrane structure. If we represent by ~* the transitive and reflexive closure of the relation ~. Clearly we have defined an equivalence relation over MS and ebrane structures are equivalence classes. It is very easy to translate this concept into graph theory. A ebrane structure is a rooted tree, where the nodes are called ebranes, the root is called sin and the leaves are called eleentary ebranes. Finally, a recursive definition of ebrane structure coing fro graph theory is given: A ebrane structure is: 1. 0 = [ ] 0 MS 2. ([ ] 0, 1,, n) where 1,, n MS for soe n 1 That is a ebrane the external one or sin- encloses a set of ebrane structures. It is considered the sae ebrane structure every perutation of the different i belonging to MS. Moreover, there is a unique lin v i connecting the ebrane [ ] 0 with the ebrane structure i = ([ ] i, i 1,, i n) where i 1,, i n MS for soe n 0. Now 0 is the ancestor of 1,, n and each one of the are connected by the lin v i. Obviously, the definition is extended to the other internal ebrane structures in a natural way. Let us say that every ebrane syste considered here has a finite nuber of ebranes, 1. Figure 1: Two equivalent ebrane structures Tree Nubering Process The purpose of the nubering process is to assign a natural nuber to each one of the different trees with nodes or ebranes and given a natural nuber associated to a tree with nodes to recover the tree structure. In [Luengo, 2008] we defined in a very siple way to assign natural nubers to ebrane structure. The process was the following: Let T = (N, E) be a tree data structure with nodes labelled in L={1,2,, }, and let P = {p 1, p 2,, p } be the set of the first natural nuber starting in 2. For the set of nodes of the tree T, it is defined the following ap: n : N P p, L (1) 12 International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, 2010 Fro this ap it was defined the nuber associated to a tree T with labels in L as follows: (T) 1 ( n ), L It is very easy to see that the process is not useful to extract the tree structure. In fact, it is possible to have several trees to which the ap gives the sae natural nuber. If we want to recover the tree structure fro a natural nuber provide by a ap, it is needed to consider soe particularities of the tree structure such as: nuber of branches, depth of each one of the branches, etc. Following with these ideas, we are going to consider branches and depth in order to assign natural nuber to nodes of the tree. First of all we are going to ap lins instead of nodes as follows: Let T = (N, E) be a tree data structure with nodes labelled in L={1,2,, }, and let P -1 = {p 1, p 2,, p -1 } be the set of the -1 first natural nuber starting in 2. Every edge or lin is nubered in pre-order starting fro left to right in depth. This process is shown in figure 2. (2) Figure 2: Nubering vertexes As we did before, for the set of vertexes of the tree T, we define the ap: And then, for the set of nodes of the tree T, it is defined the following ap: e : E P 1 (3) p, L {} : N (n n P 1 (n ), p if ) p pi L where : n is a direct descendent of the sin or root node (n ) if n is a direct descendent of n by the lin e j and n is a node of the subtree μ j i (4) Figure 3 shows this process. This process perits to ebedded inforation about tree structure into each one of the nuber associated to nodes, in particular, each one of the leaves of the tree have encoded the inforation corresponding to the branch to which they belong and the depth of each one of the. Finally, it is possible to assign a natural nuber to the tree taing into account the leaves nodes of the tree as follows: International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, Let T=(N, V) be a tree with nodes and the set of leaves L eaves ={l 1, l 2,..., l s}, 1 s then the natural nuber associated to T is defined be the expression: (T) (l ) l L eaves (5) Figure 3: nubering nodes This process perits to have soe inforation about the tree structure, that is: For each one of the leave nodes, the last prie factor is the label corresponding to the lin which connects the node with its father. The exponent of the iniu prie corresponds to the depth of the leave in the tree. Two equivalent trees have different natural nuber associated, which perits recover tree inforation independent of the equivalent relation defined before. However when all the inforation is collected into only one unique natural nuber for the tree, there is soe lost of inforation which is necessary in order to recover tree structure in the inverse process. In particular it is needed not only the nuber of branches the tree has, but also it is needed to now the depth of each one of the. Figure 4 show different trees with four leaves with different structures depending on the nuber of nodes and branches. Figure 4: Trees whit 4 leaves 14 International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, 2010 As it was said before, what is iportant for recovering tree structure inforation is the nuber of leave nodes on the tree and, also, the depth of each one of the. If we incorporate these two data into the natural nuber associated to the tree, then it is possible to recover the tree structure fro that nuber; and it is not very difficult. Incorporating the inforation of nuber of leaves and their corresponding depth into expression (5), we have: Let T=(N, E) be a tree with nodes, let L={l 1, l 2,..., l s}, 1 s be the set of leaves, let D={d 1,...,d s} be the corresponding depth for each one of the branches of the tree T, let P the set of the -1 first prie nuber, and let p 0 a prie nuber such as p 0 P -1; then the natural nuber associated to T is defined be the expression: Where for nodes is defined by expression (4) d 1 ds p p1...ps 0 (T) p ) 0 (l (6) l L Recovering tree structure In order to build a tree fro a natural nuber, there is needed that the nuber satisfied soe constrains, that is: Its factorization into prie nubers has to have different prie factors p 0 has to be nown Let p0 be a natural nuber which encodes a tree T with -1 vertexes and nodes, let p 0 be the prie which define the tree structure and let P -1 be the rest of pries appearing in the factorization of p0 ; then this nuber can be also expressed by: d p p 1...p ds 0 1 s ei (T) p p 0 i i{1,..., -1} (7) Fro this prie factorization, it is possible to recover the tree structure as follows: Pries {p i 1 i -1}, are ordered in an increasing way. Exponent of the p 0 factor encodes the nuber of leaves in the tree and the depth of each one of the. For each one of the rest of prie factor the exponent of the factor tell us about its position on the tree, factors having exponent equals to one are lins to leaves nodes on the tree, or lins to interediate nodes without branches, because they appear only once; the rest of factor tell us the nuber of ties the lin is counted in order to encode the tree structure. Let us to show soe exaples about these facts, for instance, considering the following nuber: The nuber establish the tree structure as follows: the prie factor 13 deterines that the tree has 2 leaves with 3 nodes each one. The rest of prie factors explicit the rest of the tree structure as follows: The root node is connected directly by a lin labelled with the prie nuber 2 to the next node by the left. This is the first step in order to for the first path fro the node to the leave which is two ore levels below. In order to build the path it is needed two ore nodes connected by one ore lin labelled with the prie 5. This path consues 3 ties the nuber 2, 1 tie the nuber 3 and 1 tie the nuber 5. Hence we have now 3 ties prie nuber 2, 0 ties nubers 3 and 5 and 1 tie nubers 7 and 11 in order to build the second path fro the root to the second leave of the tree. The second path starts in the root node and how we have 3 ties the nuber 2, so the path has also to pass by the node connected to the root by the lin labelled with 2 in order to consue the rest of 2 s we International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, have. Now, the path cannot pass by the lin labelled with nuber 3, we have no ore 3 s, so we need to open a second way and we consue one new prie, the next one in the factorization which is 7, and finally, we arrive to the last node of the tree trough a new lin labelled with the 11 prie nuber. On this process we have consued the rest of pries we have in the factorization, ending the building process of the tree. Figure 5: The built tree associated to 6 13(T) Next figure shows soe other exaples of this process of recovering tree structures fro a given natural nuber. In that figure it is considered that there are three leaves which are at depth of 4, 4 and 2 fro the root node. In that figure is possible to see how iportant the ultiplicity of the prie factors is in order to recover tree structures. Figure 6: Several tree structures with 3 leaves and sae depth In ters of deterining the general process for building a tree fro a given natural nuber p0 lie in (7) we propose the following algorithic description: 16 International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, 2010 p0 provides the following data: s = nuber of leaves in the tree. D = {d 1,..., d s} the set of nuber deterining the depth for each one of the leaves. P = {(p 1, e 1),..., (p -1, e -1)} the set of prie factor with their ultiplicities ordered in an increasing way. Then we consider the initial tree T to be built defined by: T = (N={1},L={ }) The idea is to add nodes lined by edges labelled by paired of natural nuber, the corresponding to the initial node and the final node as it is shows in Figure 7. Figure 7: labeling nodes and lins in the building process The algorith for building the tree fro the natural nuber p0 is the following: for (i=1; i s; i++) { n pos = 1; for (j=1 ; j d s ; j++) { tae ( p j, e j) P; if ( (n pos, p j) L) then { N = N {p j}; L = L {(n pos, p j)}; } e j --; n pos = p j ; } //end for_ j P -1 = P -1 { (p i, 0) 1-1 }; } //end for_i International Journal Inforation Theories and Applications, Vol. 17, Nuber 1, Conclusions This paper describes a way in order to transfor tree structures into natural nuber. The process is based on the very well nown gödelization process. Moreover, the process can be inverted in order to generate a tree fro a natural nuber accoplishing several constrains. However, the paper is only introductory in this field; it is needed to follow up with the study in order to deterine the real power of this approach in the study of tree structures. There are several open questions such as: Is it possible to deterine that two trees are equivalent when they are represented by natural nubers? What happens with insertion / deletion of nodes on the tree on the natural nuber? Etc. One ore proble coes fro dealing with big natural nubers. We are aware that the whole process is supported by natural nuber with a big digit nuber, and that is a proble itself in any cases. This paper is only one preliinary study of coding tree by nubers, and we hope to continue our wor with significant results and to apply to ebrane coputing and other natural coputing fields in which such data structures are relevant. Bibliography [Luengo 2008] Caren Luengo, Luís Fernández, Fernando Arroyo; P systes ödelization, International Boo Series Nuber 1, pp 29-34, ISSN , Bulgaria [Păun 2002] h. Păun, Mebrane Coputing. An Introduction, Springer-Verlag, Berlin, 2002 [Suzui 2000] Y. Suzui, H. Tanaa, On a LISP Ipleentation of a Class of P Systes, Roanian J. of Inforation Science and Technology, 3, 2 (2000), [Turing 1936] A.M. Turing, On coputable nubers, with an application to the Entscheidungsproble. Proceedings of the London Matheatical Society, 2-42, (1936-7), [P syste Web page] (july 2010) Authors' Inforation Caren Luengo Velasco Dpto. Lenguajes, Proyectos y Sisteas Inforáticos de la Escuela Universitaria de Inforática de la Universidad Politécnica de Madrid; Ctra. Valencia,. 7, Madrid (Spain); e-ail: Luis Fernández Muñoz Dpto. Lenguajes, Proyectos y Sisteas Inforáticos de la Escuela Universitaria de Inforática de la Universidad Politécnica de Madrid; Ctra. Valencia,. 7, Madrid (Spain); e-ail: Fernando Arroyo Montoro - Dpto. Lenguajes, Proyectos y Sisteas Inforáticos de la Escuela Universitaria de Inforática de la Universidad Politécnica de Madrid, Ctra. Valencia,. 7, Madrid (Spain); e-ail:

Related Search

Similar documents

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks