Optimal Dynamic Embedding of Trees into Arrays
Michael C. Loui · SIAM Journal on Computing · 1983
An optimal method for dynamically embedding trees into arrays is presented. Every multi-head tree machine of time complexity $t(n)$ can be simulated on-line by a multihead d-dimensional machine in time $O(t(n)^{1 + 1/d} /\log t(n))$. An information-theoretic argument gives the worst-case lower bound $\Omega (t(n)^{1+1/d} /\log t(n))$ on the time required.