Effiziente Algorithmen für das Separierbarkeitsproblem der alternierungsfreien Logik über unendlichen Wörtern

Abstract

Das Separierbarkeitsproblem befasst sich mit der Frage, gegeben zwei Mengen aus einer Klasse, ob es möglich ist, sie durch eine weitere Menge aus einer kleineren Klasse zu separieren. Für den Fall der Separierbarkeit von regulären Sprachen durch eine piecewise testable Sprache über unendlichen Wörtern wird in dieser Arbeit ein Entscheidungsalgorithmus mit polynomialer Laufzeit vorgestellt. Der Beweis orientiert sich an einer Arbeit über den entsprechenden Fall der Separierbarkeit über endlichen Wörtern von L. van Rooijen und M. Zeitoun.