Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2814
Authors: Pflüger, Hermann
Title: Untersuchung von Eindeutigen Büchi Automaten
Other Titles: Analysis of unambiguous Büchi automata
Issue Date: 2011
metadata.ubs.publikation.typ: Abschlussarbeit (Diplom)
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-73729
http://elib.uni-stuttgart.de/handle/11682/2831
http://dx.doi.org/10.18419/opus-2814
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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
DIP_3182.pdf3,67 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.