Das LMU Logo

Forschungsprojekt
Pro.Platz
Programmiersprachliche Aspekte
sublinearer Platzkomplexitätsklassen

TCS Logo

Inhalt

In diesem Projekt sollen Komplexitätsklassen, die durch geringen Speicherplatzbedarf gekennzeichnet sind, maschinenunabhängig und ressourcenfrei durch Verwendung von logischen und programmiersprachlichen Konzepten charakterisiert werden.

Neben theoretischen Einsichten über die Natur dieser Klassen ist dies bei der Entwicklung automatischer Analysen zur Abschätzung von Laufzeit und Platzverbrauch von Programmen nützlich. Eine andere Anwendung ist die Entwicklung spezifischer Optimierungen, die sich aus der komplexitätstheoretischen Analyse ergeben.

Für polynomielle Rechenzeit (P) und höhere Klassen sind solche Charakterisierungen seit längerer Zeit bekannt; für kleinere Klassen, die durch logarithmischen Speicherplatzbedarf definiert sind, existieren dagegen keine oder nur rudimentäre Ansätze.

Im Zusammenhang mit den erwähnten Anwendungen sind gerade diese aber von besonderem Interesse bei stark ressourcenbeschränkten Szenarien, wie Peer-to-peer Computing, eingebetteten Systemen, mobilem Code. Obwohl im Projekt die theoretische Grundlagenarbeit im Vordergrund steht, werden solche Anwendungen exemplarisch untersucht.

Beteiligte Personen

Förderung

Das Projekt wird von der Deutschen Forschungsgemeinschaft durch eine Sachbeihilfe im Umfang von einer Mitarbeiterstelle (BAT IIa) plus Sachmitteln gefördert.

Wiki English version
Last modified: Tue Sep 14 13:32:00 CEST 2005