Die Ausdrucksstärke der Logik erster Stufe mit eingebauten Prädikaten

Abstract

Diese Arbeit ist in der Theoretischen Informatik positioniert, und zwar in den Fachgebieten Komplexitätstheorie, mathematische Logik und Datenbanktheorie. Die Arbeit beschäftigt sich mit der Ausdrucksstärke der Logik erster Stufe auf Strukturen mit eingebauten Prädikaten wie z.B. lineare Ordnung, Addition und Multiplikation. Die Hauptergebnisse lassen sich den drei Teilbereichen Arithmetik und ”Zählquantoren“, die Crane Beach-Vermutung“ und Kollaps-Resultate in der Datenbanktheorie“ zuordnen. Ziel des hier vorliegenden Artikels ist, einen Einblick in die Fragestellungen und Ergebnisse zu diesen drei Themenkreisen zu geben.