Login
 Forum
 
 
Thesis topic proposal
 
Szabolcs Iván
Automaták szinkronizálása

THESIS TOPIC PROPOSAL

Institute: University of Szeged
computer sciences
PhD School in Computer Science

Thesis supervisor: Szabolcs Iván
Location of studies: SZTE
Abbreviation of location of studies: SZTE


Description of the research topic:

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.

Required language skills: angol
Further requirements: 
algoritmikus gondolkodási készség, algoritmusok
helyességigazolásának képessége

Number of students who can be accepted: 1

Deadline for application: 2017-03-31

 
All rights reserved © 2007, Hungarian Doctoral Council. Doctoral Council registration number at commissioner for data protection: 02003/0001. Program version: 1.2318 ( 2016. XI. 26. )