Time-space trade-offs for general recursion
Rutger Verbeek · 1981
A lower bound for the time-space trade-off of pebble games on PD-Graphs (which represent computations of push-down automata or recursion schemes) is proved, that is only a bit lower than the best known upper bound (the lower and upper time bound is about n · 2 logn/log(s/log n)). The best lower bound known up to now is the bound for linear recursion (about n · log n/log(s/log n) for s ≫ log n.