Automatische Analyse des Ressourcenbedarfs von imperativen Programmen

Mehr zum Buch

In der Komplexitätstheorie wird untersucht, wie man den Ressourcenbedarf von Programmen einschätzen kann, obwohl dies im Allgemeinen nicht entscheidbar ist. Das Buch präsentiert ein Verfahren zur Generierung konkreter polynomieller Längenschranken für zertifizierbare Programme, das eine obere Schranke des Ressourcenbedarfs garantiert, jedoch bei Misserfolg keine Aussage über die Existenz einer Schranke trifft. Zudem werden die Grenzen dieser automatischen Generierung analysiert und gezeigt, wie das Verfahren zur Charakterisierung der Komplexitätsklassen FP, FLINSPACE und FPSPACE beiträgt.