Automatische Analyse des Ressourcenbedarfs von imperativen Programmen

Inhaltlich unver nderte Neuauflage. In der Komplexit tstheorie ist lange bekannt, dass es im Allgemeinen nicht m glich ist Aussagen zum Ressourcenbedarf von Programmen zu ent-scheiden. So ist es z.B. unm glich zu entscheiden, ob ein Programm eine polynomielle Laufzeit besitzt. Dennoch ist es m glich Verfahren zu ent-wickeln, die manchen Programmen einen maximalen Ressourcenbedarf zerti-fizieren k nnen. 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 L ngenschranken zu zertifizierbaren Programme erm glicht. Eine solche Schranke gibt an, dass sich die L ngen aller Ausgaben des Programms durch Polynome ber den L ngen der Eingaben beschr nken lassen. Weiterhin werden die Grenzen einer solchen automatischen Generierung von polynomiellen L ngenschranken untersucht und gezeigt wie durch das vorgestellte Verfahren die Komplexit tsklassen FP, FLINSPACE und FPSPACE charakterisiert werden k nnen.