Zeiger als abstrakter Datentyp: komplexitätstheoretische und programmiersprachliche Aspekte

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

In Programmiersprachen und Logiken werden Graphen und ähnliche Datenstrukturen meist nicht als Bitfolgen sondern als strukturierte Daten behandelt. Der Zugriff auf solche Daten erfolgt dann oft durch Zeiger, mit denen zum Beispiel die Knoten in einem Graphen bezeichnet werden können. In höheren Programmiersprachen wie Java sind diese Zeiger i.d.R. abstrakt, d.h. sie können nur mit bestimmten Operationen wie Gleichheit oder Dereferenzieren manipuliert werden; ihre Repräsentation als Bitfolgen bleibt unzugänglich. In diesem Projekt soll die Programmierung mit solchen abstrakten Zeigern auf ihre Ausdrucksstärke im Sinne der Komplexitätstheorie untersucht werden. Damit sollen Erkenntnisse über die Programmierung von Algorithmen mit logarithmischem Platzbedarf (LOGSPACE) sowie polynomieller Laufzeit (PTIME) gewonnen werden. Insbesondere streben wir eine programmiersprachlich relativierte Trennung der Klassen LOGSPACE und PTIME an. Eine solche besteht aus einer Programmiersprache oder Logik, in der viele natürliche LOGSPACE Algorithmen formuliert werden können, die aber dennoch nicht ganz PTIME erfasst. Eine absolute Trennung von LOGSPACE und PTIME im Turingmaschinenmodell erscheint derzeit unzugänglich und wird hier auch nicht angestrebt. Die theoretischen Erkenntnisse sollen auch zur Verbesserung der praktischen Programmierung mit abstrakten Zeigern in Form von Spezifikationstechniken und Spracherweiterungen beitragen.