Automatische Analyse des Ressourcenbedarfs von imperativen Programmen

Inhaltlich unvernderte Neuauflage. In der Komplexittstheorie ist lange bekannt, dass es im Allgemeinen nicht mglich ist Aussagen zum Ressourcenbedarf von Programmen zu entscheiden. So ist es z.B. unmglich zu entscheiden, ob ein Programm eine polynomielle Laufzeit besitzt. Dennoch ist es mglich Verfahren zu entwickeln, die manchen Programmen einen maximalen Ressourcenbedarf zertifizieren knnen. Zertifizieren bedeutet hierbei, dass das Verfahren zwar im Erfolgsfall eine obere Schranke des Ressourcenbedarfs garantieren kann, aber bei Misserfolg nicht garantieren kann, dass eine solche Schranke nicht existiert. Dieses Buch beschreibt ein Verfahren, welches die Generierung von konkreten polynomiellen Lngenschranken zu zertifizierbaren Programme ermglicht. Eine solche Schranke gibt an, dass sich die Lngen aller Ausgaben des Programms durch Polynome ber den Lngen der Eingaben beschrnken lassen. Weiterhin werden die Grenzen einer solchen automatischen Generierung von polynomiellen Lngenschranken untersucht und gezeigt wie durch das vorgestellte Verfahren die Komplexittsklassen FP, FLINSPACE und FPSPACE charakterisiert werden knnen.