A véges automaták szinkronizálása (irányítása,
resetelése) egy, az 1960-as évek óta intenzíven kutatott terület,
melynek legismertebb, mai napig nyitott kérdése a Cerny-sejtés. Egy
(klasszikus, determinisztikus) automata szinkronizálható, ha van olyan
ún. "szinkronizáló" szava, mely konstans függvényt indukál állapotterén.
A sejtés szerint (melyet számos automataosztályra sikerült igazolni) ha
egy automata szinkronizálható, úgy van (n-1)^2 hosszú szinkronizáló
szava is. A legjobb ismert felső korlát erre a szóhosszra köbös. Hogy az
automata egyáltalán szinkronizálható-e, az egy polinomidőben eldönthető
probléma.
Újabban egyéb automatákra is kiterjesztették a fogalmat, úgy is, mint
nemdeterminisztikus, parciális, sztochasztikus, időzített vagy
tetszőlegesen súlyozott automatákra. Ezen automata-válfajok esetében
gyakran már a szinkronizálhatóság eldöntése is PSPACE-nehéz kérdés, sőt
eldönthetetlen is lehet.
A témára vállalkozó hallgató feladata a különböző automata-válfajokra
történő szinkronizálhatósági fogalmakkal kapcsolatos alapkutatás végzése.
előírt nyelvtudás: angol további elvárások: algoritmikus gondolkodási készség, algoritmusok
helyességigazolásának képessége
Bejelentkezés
