June 17, 2004
First Attempts at Factoring
We were able to factor the 3d rules into two sets of rules, both of which use only n^6 complexity. The first method factors the rule into two. This is not a complete set of rules, it is only an example of how the basic inference rule in our 3d set can be factored to be n^6. In the first rule, the children of X in the second dimension are combined to create an item for X that contains the yield of its children in the second dimension. In the second rule, the new item X is combined with the root of its third dimensional successor, U, to create the final item W. While this is similar to the original inference rules we were using, it does not encounter the same problems becuase we are not using X on both sides of the same rule. In the tree we have been working with, there are a lot of cases in which the second rule will be used with an empty U.
The second method of factoring uses items that keep the second and third dimensional yields separate. Each item has ten elements, the label, the four indices desribing the second dimensional yield, the four indices describing the third dimensional yield, and a tree identifier. We experimented with this yesterday, but generated rules that were asymptotically worse than n^6. This factorization of the 3d rules using these items remains n^6 in complexity. As of now we have not come up with a complete set of rules that work, but we are still thinking about it.
Posted by kernco at June 17, 2004 03:27 PM