Advertisement
Published in:
2011 | OriginalPaper | Chapter
Determinisierung von Büchiautomaten
Authors : Prof. Dr. Martin Hofmann, Prof. Dr. Martin Lange
Published in: Automatentheorie und Logik
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Der Titel dieses Kapitels klingt paradox; denn in Abschnitt 5.2 haben wir gesehen, dass deterministische Büchi-Automaten echt schwächer als nichtdeterministische sind. Es gibt
ω
-reguläre Sprachen, die nicht von einem DBA erkannt werden können. Somit muss es also NBA geben, die sich nicht determinisieren lassen. Die Antwort liegt in der Akzeptanzbedingung. Wie wir sehen werden, sind deterministische Rabin-, Muller- oder Paritätsautomaten ausdrucksstark genug für diese Aufgabe. Dasselbe gilt zwar auch für Streett-Automaten.Wir präsentieren hier jedoch zunächst die bekannte
Safra-Konstruktion
, die aus einem NBA einen DMA macht, den man auch leicht als DRA auffassen kann.