Diploma Thesis DIP-3182

BibliographyPflüger, Hermann: Untersuchung von Eindeutigen Büchi Automaten.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3182 (2011).
24 pages, german.
CR-SchemaF.4.1 (Mathematical Logic)
F.4.3 (Formal Languages)
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.

Full text and
other links
PDF (3758859 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Dr. M. Kufleitner
Entry dateJanuary 10, 2012
   Publ. Computer Science