Ausdrucksstärke gewichteter Automaten und Logiken

Abstract

Die Dissertation untersucht gewichtete Automaten als Erweiterung des fundamentalen Modells der endlichen Automaten sowie gewichtete Logiken als quantitative Erweiterung der monadischen Logik zweiter Stufe. Als erstes Resultat zeigen wir Zerlegungssätze für eine generische gewichtete Logik, welche sich als gewichtete Verallgemeinerungen in die Familie der Feferman-Vaught-Sätze für die klassische monadische Logik zweiter Stufe einreihen. Im zweiten Resultatkom- plex beweisen wir vier Entscheidbarkeitsresultate für das Automatenmodell der Max-Plus-Baumautomaten. Wir zeigen, dass die Äquivalenz endlich mehrdeutiger Max-Plus-Baumautomaten entscheidbar ist. Hierbei heißt ein Baumautomat endlich mehrdeutig, falls die Anzahl der Läufe des Automaten auf jedem Baum durch eine globale Konstante beschränkt ist. Für diese endlich mehrdeutigen Automaten zeigen wir des Weiteren, dass es entscheidbar ist, ob sich ein gegebener Automat auch durch einen Automaten beschreiben lässt, der höchstens einen Lauf auf jedem Baum zulässt, sowie, dass es für einen solchen eindeutigen Automaten entscheidbar ist, ob dieser sich als Maximum endlich vieler deterministischer Automaten darstellen lässt oder sogar zu einem deterministischen Automaten äquivalent ist. Das letzte Resultat verbindet Automaten und Logiken. Wir zeigen, dass sich Quantitative Monitorautomaten durch eine gewichtete Logik beschreiben lassen.