Seminár z teoretickej informatiky - Dana Pardubská (20.10.2017)

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

17. 10. 2017 13.29 hod.
Od: Rastislav Královič

Prednášajúci: Dana Pardubská

Názov: One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity

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

Abstrakt:
Tomoyuki Yamakami: One-Way Bounded-Error Probabilistic Pushdown Automata and Kolmogorov Complexity. DLT 2017
Hlavným výsledkom článku je získanie negatívnej odpovede na otázku (Hromkovič, Schnitger 2010), či jazyk palindrómov možno rozpoznávať pravdepodobnostným zásobníkovým automatom s ohraničenou chybou. Začneme rekapituláciou niektorých starších výsledkov o vzťahu tried bezkontextových jazykov a pravdepodobnostných bezkontextových jazykov s ohraničenou resp. neohraničenou chybou, následne sa sústredíme na použitie Kolmogorovskej zložitosti pri získaní hlavného výsledku článku.

web: http://kedrigern.dcs.fmph.uniba.sk/STI2
rss: http://kedrigern.dcs.fmph.uniba.sk/STI2/rss.php