Po rozwiązaniu w 2008 roku przez Trahtmana tzw. Road Coloring Problem (RCP) -
problemu otwartego od ponad 30 lat, powstał szereg nowych problemów
dotyczących związków RCP z synchronizacją automatów skończonych. Na
konferencji 'Cerny Conjecture' (Wrocław, 2008) prof. M. Volkov
przedstawił listę takich zagadnień.
W moim wystąpieniu chciałbym opisać rozwiązanie jednego z nich, mianowicie
NP-zupełność następującego problemu:
Wejście: skierowany (multi)graf G o stałym stopniu krawędzi
wychodzących, liczba naturalna m
Wyjście: TAK, jeśli istnieje synchronizowalne kolorowanie G oraz słowo
synchronizujące
o długości m.
|
Seminaria \ Seminarium Zakładu T. P. I. \ 16.04.2009 Adam Roman
