Programmiersprachliche Aspekte sublinearer Platzkomplexitätsklassen

点击翻译按钮获取中文摘要

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.