Automaten auf unendlichen Objekten

Automaten auf unendlichen Objekten lesen Eingaben, die niemals enden, wie unendliche Wörter oder unendliche Bäume, und akzeptieren diese entsprechend den Zuständen oder Übergängen, die unendlich oft besucht werden, wodurch sie das mathematische Gerüst für die Argumentation über fortlaufende, nicht terminierende Systeme bereitstellen.

Definition

Ein Omega-Automat ist eine endliche Zustandsmaschine, deren Läufe unendlich sind, wobei die Akzeptanz durch eine Bedingung an die Menge der unendlich oft besuchten Zustände definiert ist; solche Automaten erkennen Mengen unendlicher Wörter oder Bäume, die als omega-reguläre Sprachen bezeichnet werden.

Scope

Dieses Thema behandelt Büchi-, Muller-, Rabin- und Paritätsautomaten über unendlichen Wörtern, die Akzeptanzbedingungen, die sie unterscheiden, Determinierungs- und Komplementierungsresultate, Automaten über unendlichen Bäumen sowie die tiefen Verbindungen zwischen diesen Automaten, der monadischen Prädikatenlogik zweiter Stufe und unendlichen Spielen, die in Synthese und Verifikation verwendet werden.

Core questions

• Wie kann eine endliche Maschine eine Eingabe akzeptieren oder ablehnen, die kein Ende hat?
• Warum unterscheiden sich nichtdeterministische und deterministische Büchi-Automaten in ihrer Ausdruckskraft?
• Wie stehen Automaten über unendlichen Objekten in Beziehung zu Logiken zur Spezifikation des Systemverhaltens?
• Was macht die Komplementierung dieser Automaten schwierig, und warum ist das von Bedeutung?

Key theories

Büchi-Akzeptanz und omega-reguläre Sprachen

Ein Büchi-Automat akzeptiert ein unendliches Wort, wenn ein bestimmter akzeptierender Zustand unendlich oft besucht wird, und die so erkannten Sprachen, die omega-regulären Sprachen, stimmen mit denen überein, die in der monadischen Prädikatenlogik zweiter Stufe über den natürlichen Zahlen definierbar sind.

Determinierung und die Paritätsbedingung

Nichtdeterministische Büchi-Automaten können im Allgemeinen nicht deterministisch gemacht werden, ohne die Akzeptanzbedingung zu ändern, aber Safras Konstruktion wandelt sie in deterministische Rabin- oder Paritätsautomaten um, was für die Komplementierung und für das Lösen von Spielen unerlässlich ist.

Clinical relevance

Omega-Automaten bilden das algorithmische Rückgrat des Model-Checking: Ein reaktives System und eine temporallogische Eigenschaft werden jeweils in Automaten über unendlichen Wörtern übersetzt, und die Überprüfung der Eigenschaft reduziert sich auf einen Leerheitstest, was eine automatisierte Verifikation von Hardware, Protokollen und nebenläufiger Software ermöglicht.

History

Büchi führte Automaten auf unendlichen Wörtern um 1960 ein, um die monadische Prädikatenlogik zweiter Stufe der natürlichen Zahlen zu entscheiden. McNaughton zeigte, wie man sie mit stärkeren Akzeptanzbedingungen determinieren kann, und Rabin erweiterte die Theorie auf unendliche Bäume. Diese Ergebnisse wurden nach dem Einzug der Temporallogik in die Informatik Ende der 1970er Jahre zentral für die Verifikation.

Key figures

• J. Richard Büchi
• Robert McNaughton
• Michael Rabin
• Shmuel Safra

Seminal works

• thomas1990
• graedel2002

Frequently asked questions

Wie kann eine Maschine eine unendliche Eingabe akzeptieren?

Die Akzeptanz wird nicht durch das Erreichen eines Endzustands am Ende definiert, da es kein Ende gibt, sondern dadurch, welche Zustände wiederkehren. Ein Büchi-Automat akzeptiert beispielsweise, wenn er während seines endlosen Laufs unendlich oft einen bestimmten akzeptierenden Zustand durchläuft.

Warum sind diese Automaten für die Verifikation wichtig?

Nicht-terminierende Systeme wie Betriebssysteme und Netzwerkprotokolle werden natürlicherweise durch unendliche Verhaltensweisen modelliert. Eigenschaften wie „das System blockiert niemals“ oder „jede Anfrage wird schließlich bedient“ werden zu omega-regulären Sprachen, sodass deren Überprüfung auf Automatenoperationen reduziert wird, die ein Model-Checker automatisch durchführen kann.