Optimal On-Line Simulations of Tree Machines by Random Access Machines
Michael C. Loui, David R. Luginbuhl · SIAM Journal on Computing · 1992
This paper shows that every tree machine of time complexity t can be simulated on-line by a log-cost random access machine (RAM) of time complexity $O((t\log t)/\log \log t)$. Using information-theoretic techniques, it is shown that this simulation is optimal. It is also shown that every tree machine can be simulated by a unit-cost RAM in real time.