Untersuchung von Eindeutigen Büchi Automaten

Abstract

Im Gegensatz zu Automaten über endlichen Wörtern haben deterministische Büchi Automaten nicht die selbe Ausdrucksstärke wie nichtdeterministische Büchi Automaten. Für nichtdeterministische Büchi Automaten sind häufig nur erheblich schlechtere Algorithmen für die verschiedenen Berechnungsprobleme bekannt. Aus diesem Grund sind Einschränkungen von nichtdeterministischen Büchi Automaten interessant, welche immer noch die volle Ausdrucksstärke haben, dabei jedoch ähnlich effiziente Verfahren wie deterministische Büchi Automaten erlauben. Eine solche Einschränkung bilden die stark eindeutigen Büchi Automaten von Carton und Michel. In dieser Arbeit wird ein ähnlicher Automat mit geringerer Komplexität vorgestellt. Eine noch gerinere Komplexität haben die in dieser Arbeit vorgestellten "stark k-eindeutige Büchi Automaten", die zwar nicht eindeutig nach der allgemeinen Definition sind, jedoch ähnliche Eigenschaften wie stark eindeutige Büchi Automaten zeigen, insbesonder bei der Komplementbildung. Weiterhin wird in dieser Arbeit für eine spezielle Sprachklasse ein deterministischer, stark eindeutiger Büchi Automat beschrieben. Für alle diese Automaten wird, ausgehend von der starken Erkennung einer Sprache, eine Konstruktion gezeigt.