9.02.2006

Hipoteza Cernego i problemy synchronizacji automatów skończonych

Automat A=(Q, A, δ) jest synchronizujący, jeśli istnieje takie słowo w ∈ A^*, pod wpływem, którego wszystkie stany ze zbioru Q przechodzą do jednego i tego samego stanu. Hipoteza Cernego głosi, ze jeśli n-stanowy automat jest synchronizujący, to długość najkrótszego spośród jego słów synchronizujących nie przekracza (n-1)². W referacie przedstawione będą wyniki badań zawartych w przygotowywanej rozprawie doktorskiej, a związanych właśnie z problemem synchronizacji i hipoteza Cernego:

1. wyniki eksperymentów numerycznych i zbadanie wpływu rozmiaru alfabetu na długość słowa synchronizującego
2. nowa klasa automatów spełniających hipotezę Cernego
3. nowe wielomianowe algorytmy znajdujące możliwie krótkie słów synchronizujące oraz porównanie tych algorytmów z algorytmami zachłannymi Eppsteina.