Seminár Ústavu informatiky

Prednáška

Operácia Hviezdička-Doplnok-Hviezdička na Bezpredponových Jazykoch

RNDr. Juraj Šebej
Ústav informatiky, PF UPJŠ

28. októbra 2015 (streda) o 13:30
SA1C03 (P/03), PF UPJŠ

Abstrakt

Zaoberáme sa stavovou zložitosťou zloženej operácie hviezdička-doplnok-hviezdička na bezpredponových jazykoch. V prvej časti sa pozrieme na historický vývoj až po formuláciu problému. Ďalej budeme prezentovať vlastné výsledky, tesnú hranicu 2^(n-3)+2 na binárnej abecede. V prípade unárnej abecedy vieme dokonca stavovú zložitosť pre každý jazyk.