Die Kostenanalyse von Programmen ermöglicht es, den für die Ausführung eines Programmes notwendigen Ressourcenbedarf, wie zum Beispiel Zeit oder Speicher statisch, zu bestimmen. Den Ressourcenbedarf eines Programms bezeichnet man auch als die Kosten des Programms. Die Programmkosten hängen im Allgemeinen von Eingabeparametern (den Eingabedaten) ab. Das Bestimmen einer Funktion, die in Abhängigkeit von den Eingabeparametern die exakten Kosten eines Programms angibt, ist in der Regel nicht möglich. Stattdessen versucht man bei der Kostenanalyse Funktionen zu ermitteln, die obere und untere Schranken für die Kosten eines Programmes darstellen.

Viele der existierenden Ansätze zur Kostenanalyse gehen das Problem in zwei Stufen an. Zuerst wird das zu analysierende Programm in eine abstrakte Integer-Repräsentation überführt, in welcher der Ressourcenbedarf/-verbrauch explizit dargestellt ist. In der zweiten Stufe wird diese abstrakte Repräsentation analysiert und obere bzw. untere Schranken bestimmt. Der Vorteil dieses Ansatzes ist, dass die zweite Stufe unabhängig von der Programmiersprache und der betrachteten Ressource (Zeit, Speicher usw.) ist. Dies ermöglicht den Einsatz der für die zweite Stufe entwickelten Techniken und Werkzeuge zur Analyse von Programmen in unterschiedlichsten Programmiersprachen bzgl. des Verbrauchs unterschiedlich Ressourcen. Kostenrelationen bieten sich als eine Wahl für die abstrakte Repräsentationen der Programme an. Sie ähneln Programmen aus der Constraint-logischen Programmierung, die mit Kostenannotationen versehen sind. Kostenrelationen erlauben es ferner, funktionale sowie imperative Programme auf einfache Art zu repräsentieren.

Existierende Kostenanalysen haben eine Reihe von Nachteilen betreffend der Analyse von Programmen mit komplexem Kontrollfluss sowie bei der Bestimmung amortisierter Komplexität zur Beschreibung von Szenarien, bei denen die Gesamtkosten eines Programmes kleiner sind als die Summe der asymptotischen Einzelkosten. In dieser Arbeit werden die Einschränkungen der existierenden Ansätze identifiziert und eine neuartige Analyse entwickelt, die diese überwindet. Die entwickelte Analyse bestimmt obere und untere Schranken für in Kostenrelationen überführte Programme. Sie besteht aus den folgenden drei Teilen:

1. Im ersten Teil der Analyse werden wechselseitig-rekursive Kostenrelationen in äquivalente Kostenrelationen überführt, die nur noch einfache Rekursionen enthalten. Ausserdem werden weitere Vereinfachungsschritte durchgeführt.

2. Im zweiten Teil werden die Kostenrelationen mit Hinblick auf den Kontrollfluss verfeinert. Die Verfeinerung partitioniert die Kostenrelationen in eine endliche Menge von Ausführungsmustern, sogenannten Ketten (Chains), die alle möglichen Ausführungen beschreibt. Die Verfeinerung gibt des weiteren präzise Invarianten für die einzelnen Ketten an, eliminiert nicht erreichbare Programmpfade und beweist die Terminierung des Programms.

3. Im dritten Teil der Analyse werden schließlich Schranken für die Kosten auf kompositionelle Art und Weise berechnet. Zu diesem Zweck wird eine neuartige Art der Kostenrepräsentation, genannt Kostenstrukturen, entwickelt und vorgestellt. Kostenstrukturen erlauben es, die Berechnung komplexer Schranken auf das Lösen einfacher Constraints mit Hilfe linearer Programmierung zu reduzieren. Kostenstrukturen können polynomielle obere und untere Schranken von Programmen repräsentieren und unterstützen dabei max- und min-Operatoren.

Die entwickelte Analyse wird als korrekt bzgl. einer neuen Semantik von Kostenrelationen bewiesen. Die im Rahmen dieser Arbeit entwickelte neue Semantik erlaubt es, zwischen terminierenden und nicht-terminierenden Programmenausführungen zu unterscheiden und modelliert nicht terminierende Programmausführungen akkurat.

Schließlich wurde die neue Kostenanalyse im Werkzeug CoFloCo implementiert und extensiv evaluiert. Die Evaluierung vergleicht CoFloCo mit anderen, dem aktuellen Stand der Forschung entsprechenden Tools anhand einer Vielzahl von Benchmarks. Diese Benchmarks bestehen aus imperativen und funktionalen Programmen sowie aus Termersetzungssystemen. CoFloCo zeigt durchgehend eine sehr gute Leistung in allen Kategorien und demonstriert damit die Leistungsfähigkeit und Vielseitigkeit der entwickelten Kostenanalyse.