Theory Group

External Tree Form

Lemma

If X is the root of an i-dimensional structure, it has no j-dimensional successor for j < i.

Proof

When i = 0 or i = 1, this is trivially true. An i-dimensional tree consists of a root X and an (i-1)-dimensional yield. If X has any other successor, then it violates this definition and is not the root of an i-dimensional tree.

Corollary

If X is an i-dimensional successor (in threaded form) then X has no j-dimensional successor for j < i - 1.

Proof

X is a root of an (i-1)-dimensional yield. By the lemma, the root of an (i-1)-dimensional structure has no j-dimensional successors for j < i - 1.

Inductive Definition for Representation of External Trees

• ~ denotes an "empty root" of any dimension.
• For d >= i >= 0, if r(d-1)...r(i-1) denotes d-1,..., i-1 dimensional roots in a d-dimensional structure, then X(r(d-1), ..., r(i-1)) denotes an i-dimensional root in a d-dimensional structure.
• Note that the representation of a 0-dimensional root includes a -1 dimensional child that must always be indicated by a ~. This distinguishes the node from a 1-dimensional root whose successors would only range from a (d-1)-dimensional root to a 0-dimensional root.
• Because of the lemma above, we are only ranging to i-1 because we don't have to represent trees that cannot exist. The omission of the successors less than i-1 gives us the ability to distinguish between the different dimensionality of the nodes as well as an isomorphism that allows structures to be interpreted as higher dimensional structures with the lower dimensions absent.

We wish to add to this representation a way to indicate the tree heads. One way to do this is to keep track of the heights of each node to denote the allowed range of tree head indicators. This is using the Integer Labeled Nodes method referred to earlier. This is our first attempt, however we are planning on modifying the method to keep track of spine lengths rather than heights in the trees.

We can annotate this representation to show the height of each node in each dimension of their local structures. Let X<h_d-1,...,h_i-1>(r_d-1<h^d-1_d-1>, r_d-2<h^d-2_d-1,h^d-2_d-2>, ..., r_i-1<h^i-1_d-1,...,h3^i-1_i-1>) denote the local structure where, given i <= k <= d-i+1, h_d-k = Max(h^j_d-k if j != d-k, otherwise h^j_d-k+1), ranging over i-1 <= j <= d-k. h_d-1 is the height of X in the d-1 dimension. Note that ~ is taken to be a height of -1.

This formula is correct because every node's height is determined by looking at the maximum height of all its successors, keeping in mind that the node's height in a given dimension must be at least one greater than the height of its successor in that dimension.

Here is an example:

Tree w/o Heights:
A(B(~,C(~,F(~,~,G(~,~,~,H)),D(~,M(~,~,~,~),N(~,~,~,~),E(~,K(~,~,~,~), J(~,~,~,~),I(~,L(~,~,~,~),~,~))))))

Tree w/ Heights:
A<1>(B<0,2>(~,C<0,1,2>(~,F<0,1,1>(~,~,G<0,0,0,1>(~,~,~,H<0,0,0,0>)), D<0,1,1,2>(~,M<0,0,0,0>(~,~,~,~),N<0,0,0,0>(~,~,~,~),E<0,1,1,1>(~, K<0,0,0,0>(~,~,~,~),J<0,0,0,0>(~,~,~,~),I<0,1,0,0>(~,L<0,0,0,0>(~,~,~,~),~,~))))))
Posted by kernco at June 29, 2004 06:22 PM