[Zurück]

J. Blieberger, R. Lieger:
"Worst-Case Space and Time Complexity of Recursive Procedures";
Real-Time Systems, 11 (1996), S. 115 - 144.

The purpose of this paper is to show that recursive procedures can be used
for implementing real-time applications without harm,
if a few conditions are met.
These conditions ensure that upper bounds for space and time requirements can be
derived at compile time.
Moreover they are simple enough such that many important recursive
algorithms can be implemented,
for example Mergesort or recursive tree-traversal algorithms.

In addition, our approach allows for concentrating on essential properties
of the parameter space during space and time analysis.
This is done by morphisms that transfer important properties
from the original parameter space to simpler ones,
which results in simpler formulas of space and time estimates.

http://dx.doi.org/10.1007/BF00365315