We have been considering the number of new automaton rules that will be added depending on the number of links which are outside of the branching factor. In comparing full 3-dimensional n-branching local trees to 3d (n-1)-branching local trees we have come to some conclusions. We consider all links that are not in an (n-1)-branching local tree but are in a n-branching local tree illegal. We then considered the number of illegal links in each dimension. in a 3d local tree converting from 3-branching to 2-branching there are 3 illegal 2d links and 7 illegal 1d links. But, as we fix each 2d link we will fix a 1d link so after we fixed the three 2d links there will only be 4 1d links left to fix. The method of decreasing the branching factor of an automaton by embeding local trees into sets of local trees is only meant to fix one link per new rule, but in fact fixes one link in each dimension less than or equal to d. Taking this into account the number of new rules required turns out to be equal to the number of illegal 1d links.Asymptotically the number of rules grows at the same speed as the number of new nodes because the number of 1d links is a constant factor of the number of total links.
Posted by lemanal at August 3, 2004 04:51 PM