August 02, 2004
Asymptotic Growth of n-branching Local Trees
Through drawing many comlicated trees and counting nodes, we were eventually able to discover a pattern and come up with a formula for calculating the maximum number of nodes allowed in a d-dimensional n-branching local tree. The formula is recursive.
Notation:
Nodes(d, n) = The maximum number of nodes in a d-dimensional, n-branching local tree.
Base:
Nodes(2, n) = n + 1
Recursion:
Nodes(d, n) = ( (Nodes(d - 1, n) - 1) * (n - 1) ) + 2
The complexity of an n-branching tree as the dimension increases is O(x^(n-1)). We are more interested, however in the complexity of d-dimensional tree as n increases. We do not have proof using the recursive equation, since the recursion is done with n being held constant, but from looking at the chart we constructed, it appears that it is O(x^(d-1)). We will look at this more closely later.
The number of illegal links in a given local tree is equal to Nodes(d, n) - Nodes(d, 2). Nodes(d, 2) has no illegal links, since the notion of an illegal link is a link that makes the branching factor greater than two. In fact, the tree it represents contains the only possible legal links. Since any higher branching tree would also contain these links, we must subtract them from the number. Also, since we know there aren't any more legal links possible, we know that we don't need to subtract anything more.
Since every illegal link is turned into a new automaton rule, the size of the automaton using embedding would increase with the same complexity as the number of nodes of the n-branching tree. We did notice, however, that sometimes a new rule can eliminate more than one illegal link. In the maximally filled n-branching tree, removing an i-dimensional illegal link will remove i illegal links. This is because removing a 2-dimensional illegal link will move the 1-dimensional illegal link that was a part of that local tree into a legal position. With a 3-dimensional illegal link, the same thing happens with a 2- and 1-dimensional link in the local tree. Looking at the tree below, fixing the illegal link labeled 'A' will fix the link labeled 'a' legal as well. Fixing the link 'B' will fix both links labeled 'b' legal. However, we don't believe this decreases the asymptotic complexity. This is another thing we will have to look at more closely.
Here is a chart we made. Some of it was made by drawing the trees by hand. After we used it to come up with the formula, we filled the rest in with the formula.
