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

Seminár z teoretickej informatiky - Rastislav Královič (11.10.2019)

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


09. 10. 2019 09.27 hod.
Od: Rastislav Královič

Prednášajúci: Rastislav Královič

Názov: Konečné automaty s radou III

Termín: 11.10.2019, 11:00 hod., M/213


Abstrakt:
Seminár zreferuje o nových čiastočných výsledkoch v modeli neuniformných konečných automatov, t.j. automatov s pomocnou (oracle) páskou, ktorej obsah je funkciou dĺžky vstupu. Dokážeme hypotézu z predchádzajúcej časti, že 1-smerné deterministické automaty nevedia využiť superpolynomiálnu radu a ukážeme niekoľko predbežných výsledkov o randomizácii.

web: https://beda.dcs.fmph.uniba.sk/seminar