Top-down Ergänzung von Automaten auf endlichen Bäumen

Wir präsentieren eine neue Ergänzungsconstruction für nichtdeterministische Automaten auf endlichen Bäumen. Die traditionelle Ergänzung beinhaltet die Determinierung des entsprechenden Bottom-up-Automaten (merken Sie, dass top-down deterministische Automaten weniger leistungsfähig sind als nichtdeterministische Automaten, während bottom-up deterministische Automaten gleich leistungsfähig sind). Die Konstruktion funktioniert direkt in einer Top-down-Weise, daher ohne Determinierung. Die Hauptvorteile dieser Konstruktion sind: (i) im speziellen Fall endlicher Wörter reduziert sie sich auf die Standard-Mengen-Konstruktion (was bei der traditionellen Bottom-up-Ergänzung nicht der Fall ist), und (ii) sie veranschaulicht das zentrale Argument des Ergänzungslemma für unendliche Bäume, das im Beweis des Rabinschen Baumtheorems zentral ist, in einem einfacheren Rahmen, in dem Probleme im Zusammenhang mit Akzeptanzbedingungen für unendliche Wörter und der Determiniertheit unendlicher Spiele nicht vorhanden sind.