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

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

06. 10. 2021 10.08 hod.
Od: Rastislav Královič

Prednášajúci: Dana Pardubská

Názov: O neregulárnych deterministických bezkontextových jazykoch (DCFL')

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

Abstrakt:
Problém je C-ľahký ak môže byť redukovaný na každý problém v triede C. Zadefinujeme tt-redukciu Mealyho strojmi a ukážeme, že pri tejto redukcii je jazyk L_# = {0^n1^n} DCFL'-ľahký a jazyk L_R = {wcw^R} DCFL'-ľahký nie je. Konštrukcia redukcie pre L_# vychádza z alternatívnej charakterizácie triedy DCFL'.

Prezentované sú výsledky podľa článku P. Jančar, J. Šíma (MFCS 2021) s poznámkami podľa príspevkov F. Mráz, D. Pardubská, M. Plátek, D. Prusa, J. Šíma (ITAT 2020/21)

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