Seminár z teoretickej informatiky - Rastislav Královič
v piatok 2.3.2018 o 11:00 hod. v miestnosti M/213
Prednášajúci: Rastislav Královič
Názov: Konečné automaty s radou II.
Termín: 2.3.2018, 11:00 hod., M/213
Abstrakt:
Model neuniformných konečných automatov (a.k.a. automaty s radou) bol už na seminári pred časom prezentovaný. V prednáške predstavíme niekoľko nových výsledkov a otvorených problémov, ktoré sú výsledkom spoločnej práce s P. Ďurišom, Ri. Královičom a R. Korbašom. Zameriame sa na vzťah determinizmu a nedeterminizmu - kým nedeterministické automaty vedia s exponenciálnou radou akceptovať ľubovoľný jazyk (a sú jazyky, ktoré exponenciálnu radu potrebujú), deterministické automaty nedokážu akceptovať niektoré jednoduché jazyky bez ohľadu na veľkosť rady. Zaujímavá otázka je, akú veľkú radu dokážu deterministické automaty využiť: ukážeme, že ak sa jazyk nedá akceptovať s exponenciálnou radou, nedá sa akceptovať vôbec. Máme hypotézu, že deterministický automat nedokáže využiť viac ako polynomiálnu radu. Ukážeme tiež hierarchie v závislosti od veľkosti rady pre nedeterministické automaty.
web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php