Fakulta matematiky, fyziky
a informatiky
Univerzity Komenského v Bratislave

Seminár z teoretickej informatiky - Rastislav Královič

v piatok 2.3.2018 o 11:00 hod. v miestnosti M/213


27. 02. 2018 09.12 hod.
Od: Rastislav Královič

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