Computing on a free tree via complexity-preserving mappings
Bernard Chazelle · 1984
It appears that in a number of cases computing over free trees is no more difficult than computing over linear lists. In the arithmetic model, we have established a strict equivalence between the interval query problem and its generalization on a tree structure. In the reference machine model, the concept of efficiency is traditionally captured by the class of retrieval problems which can be solved in O(nP0LY LOG(n)) space and O(POLYLOG(n)) time. We have shown that in a number of examples this class is closed under transformations from lists to trees. Characterizing the set of problems and techniques for which this holds is an interesting open problem.