| 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.
|
| 21. 3. 2024 |
Miroslav Repický – Kapacity na $\omega$ |
|
Abstrakt:
Skúmame koncept kapacity na $\omega$ a kapacitné ideály.
Zaoberáme sa postupnosťami kapacít a otázkou, ktoré $F_{\sigma\delta}$ ideály
sú určené postupnosťami kapacít.
|
| 18. 4. 2024 |
Peter Eliaš – Konštrukcia voľného ortomodulárneho posetu nad daným ortoposetom, II |
|
Abstrakt:
Pripomenieme konštrukciu voľného ortomodulárneho posetu nad daným ortoposetom.
Pre daný ortoposet $P$ uvažujme jazyk $\mathcal{L}_P$ obsahujúci unárnu operáciu $'$, binárnu operáciu $\vee$ a konštantu $c_p$ pre každý prvok $p\in P$.
Nech $\mathcal{T}_P$ je množina všetkých termov v jazyku $\mathcal{L}_P$.
Ak $f\colon P \to Q$ je homorfizmus z ortoposetu $P$ do ortomodulárneho posetu $Q$, vieme pre niektoré termy $\tau\in\mathcal{T}_P$ definovať ich hodnotu $\mathrm{val}_f(\tau)$.
To umožňuje definovať množinu "dobre definovaných termov" $\mathcal{W}_P\subseteq\mathcal{T}_P$, ako aj operácie $'$, $\vee$ na množine $\mathcal{W}_P$.
Definícia obsahuje podmienku s univerzálnym kvantifikátorom tvaru "pre všetky homomorfizmy z $P$ do nejakého ortomodulárneho posetu platí ...".
Voľný ortomodulárny poset nad ortoposetom $P$ vieme potom definovať ako kvocientovú štruktúru $(W_P,',\vee)/{\sim}$ pre vhodnú kongruenciu $\sim$.
Naším cieľom je túto definíciu nahradiť jednoduchšou podmienkou závisiacou iba od daného ortoposetu, bez kvantifikácie cez všetky homomorfizmy.
Využijeme pozorovanie, že príslušnosť termu k množine $\mathcal{W}_P$, ako aj výsledky operácií medzi termami, závisia iba od nerovností platiacimi medzi prvkami ortoposetu.
Toto pozorovanie je v jazyku teórie kategórií vyjadrené pomocou existncie pushout-ov.
|
| 16. 5. 2024 |
Irena Jadlovská – Oscilácie lineárnych diferenciálnych rovníc tretieho rádu: nedávne výsledky a otvorené problémy |
|
Abstrakt:
V predmetnom príspevku najprv stručne uvedieme základné poznatky z kvalitatívnej teórie lineárnych diferenciálnych rovníc s oneskorením tretieho rádu.
Ďalej ukážeme, ako aplikovať našu novú metódu iteratívne vylepšených monotónností neoscilatorických riešení na stanovenie ostrých horných a dolných odhadov
pre triedu kladných neohraničených riešení. Nakoniec načrtneme riešenie obzvlášť náročného otvoreného problému - získania dolných odhadov
takzvaných Kneserových riešení - t.j. kladných ohraničených riešení so striedavými znamienkami derivácií.
|
| 30. 5. 2024 |
František Silváši (Consequentia) – Interaktívne dôkazové asistenty |
|
Abstrakt:
V tejto prezentácii predstavíme úvod do interaktívnych dôkazových asistentov, konkrétne si vyberieme Lean. Predstavíme jeho metateóriu a to, ako ju aplikovať
na mechanickú konštrukciu dôkazov. Demonštrujeme najdôležitejšie koncepty na Peanovej konštrukcii prirodzených čísel, ktoré využijeme na definíciu jednoduchých operácií,
o ktorých dokážeme vybrané vlastnosti.
|