Seminár detašovaného pracoviska Matematického ústavu SAV v Košiciach

···   2020-21   •   2022   •   2023   •   2024
 
najbližšie:
21. 3. 2024 Miroslav Repický
 
predchádzajúce:
11. 1. 2024 Michal Hospodár – Operačná zložitosť v podtriedach regulárnych jazykov
Abstrakt: Stavová zložitosť regulárnej operácie je funkcia, ktorá veľkostiam deterministických konečných automatov pre jazyky vstupujúce do operácie priradí najväčšiu zo stavových zložitostí jazykov, ktoré sú výsledkom tejto operácie. Študujeme stavovú zložitosť prieniku, zjednotenia, zreťazenia, uzáveru a zrkadlového obrazu na triedach kombinačných jazykov, konečne generovaných ľavých ideálov, symetricky definitných, hviezdových, kométových, obojstranne kométových, usporiadaných, bezhviezdových a mocniny separujúcich jazykov. Dostaneme presné stavové zložitosti vo všetkých prípadoch. Všetky naše dosvedčujúce jazyky, s výnimkou zrkadlového obrazu na konečne generovaných ľavých ideáloch a usporiadaných jazykoch, sú popísané nad konštantnou abecedou.
25. 1. 2024 Galina Jirásková – Operačná zložitosť: Cena konverzie NFA na DFA
Abstrakt: Skúmame operačnú zložitosť za predpokladu, že argumenty sú dané ako nedeterministické konečné automaty a výsledný jazyk je reprezentovaný deterministickým konečným automatom. Ukazujeme, že známe horné odhady zložitostí pre booleovské operácie a zreťazenie sú dosiahnuté ternárnymi jazykmi, a dokazujeme, že v binárnom prípade sú asymptoticky tesné. Pre strojové zreťazenie a štvorec dosiahneme presné hodnoty zložitostí pomocou jazykov nad abecedou veľkosti štyri (strojové zreťazenie) a desať (štvorec). Ukazujeme tiež výsledky pre syntaktickú zložitosť a druhú odmocninu jazyka.
22. 2. 2024 Jozef Pócs – O grafe deliteľov nuly čiastočne usporiadaných množín
Abstrakt: Je známe, že tzv. Beckova domnienka, t. j. rovnosť konečných klikových a chromatických čísel grafu deliteľov nuly, platí pre čiastočne usporiadané množiny. Uvedieme jednoduchý priamy dôkaz tohto faktu. Skúma sa aj prípad, keď sa vynechá predpoklad konečnosti klikového čísla. Ukáže sa, že v tomto prípade domnienka vo všeobecnosti neplatí a uvedú sa niektoré protipríklady.