Le problème de la synchronisation et la conjecture de Černý. (French) Zbl 0543.68039

Pin, Jean-Eric

Quad. Ric. Sci. 109, 37-48 (1981).

Wir geben einen Überblick über das folgende Problem (das Synchronisationsproblem). Sei \(A=(Q,X)\) ein endlicher Automat. Jedes Wort m aus \(X^*\) definiert eine Funktion von Q in Q; der Rang von m in A ist die ganze Zahl Car\(d\{\) qm: \(q\in Q\}\). Ein Wort des Rangs 1 ordnet jedem der Zustände einen einzelnen Zustand zu und wird ein synchronisierendes Wort genannt (falls ein solches Wort existiert, so wird der entsprechende Automat synchronisierend genannt). Sei A ein Automat mit n Zuständen. Černý hat vermutet, daß, falls A synchronisierend ist, ein synchronisierendes Wort der Länge \(\leq(n-1)^ 2\) existiert. Eine Verallgemeinerung dieser Vermutung ist, daß, falls in A ein Wort des Rangs \(\leq k\) existiert, es ein synchronisierendes Wort der Länge \(\leq(n-k)^ 2\) in A gibt. (Zusammenfassung des Autors.)

Reviewer: H.-H.Homuth

MSC:

68Q45

Formal languages and automata

Keywords:

synchronization problem; rank of a word; synchronizing word; synchronizing automata