Bejelentkezés
 Fórum
 
 
Témakiírás
 
Iván Szabolcs
Automaták szinkronizálása

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

témavezető: Iván Szabolcs
helyszín: SZTE
helyszín rövidítés: SZTE


A kutatási téma leírása:

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

felvehető hallgatók száma: 1

Jelentkezési határidő: 2017-03-31

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2318 ( 2016. XI. 26. )