Eine Vermutung im Zusammenhang mit der Cerny-Vermutung - Gegenbeispiel / Referenzanforderung

Die Cerny-Vermutung ist die Aussage, dass jeder Synchronisationsautomat mit Zuständen höchstens ein Synchronisationswort der Länge . Die beste aktuelle Obergrenze für die Länge eines Synchronisationsworts ist . Lassen Sie uns sagen , dass zwei Staaten verschmolzen mit einem Wort , wenn das Wort die beiden Zustände in den gleichen Zustand nimmt. Ein Argument vom Typ Pumping Lemma zeigt, dass in einem Synchronisationsautomaten zwei beliebige Zustände durch ein Wort mit einer Länge von höchstens . Angenommen, die folgende Vermutung ist wahr.$n$$(n-1)^2$$O(n^3)$$n^2$

Vermutung. Jede Teilmenge von Zuständen enthält zwei Zustände, die durch ein Wort der Länge (sagen wir) höchstens . Oder allgemeiner enthält jede große Menge von Zuständen zwei, die durch ein Wort der Länge .$k$$n^2/k$$o(n^2)$

Dann können wir die folgende Strategie zum Konstruieren eines Synchronisationsworts betrachten. Wir beginnen mit allen Zuständen. Nach der obigen Vermutung gibt es ein kurzes Wort, das zwei Zustände zusammenführt, und wir machen dies zum Anfang unseres Synchronisationsworts. Wir können den DFA mit diesem Wort ausgehend von allen Zuständen ausführen, und wir erhalten eine Reihe von höchstens Endzuständen. Wir wiederholen dies mit diesen Endzuständen als unseren neuen Startzuständen. Nachdem wir dies ausreichend oft wiederholt haben, erhalten wir nur einen Endzustand. Angesichts der obigen Vermutung hätten wir eindeutig eine bessere Grenze als für die Länge des kürzesten Synchronisationsworts.$n$$n-1$$O(n^3)$

Das Obige motiviert die folgenden Fragen:

1. Gibt es bekannte Gegenbeispiele zu dieser Vermutung? Cernys ursprüngliche Konstruktion (siehe Seite 18 ) entspricht der Aussage der Vermutung.
2. Könnten Sie eine Referenz angeben, in der ähnliche Ideen untersucht werden?

Ich habe eine teilweise Antwort auf Frage 2 gefunden. Die gleiche Idee wird in den letzten 10 Minuten dieser Vorlesung diskutiert .