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

<<  2017

26. 1. 2017 – doc. RNDr. Ján Borsík, CSc. – Body pórovitospojitosti

Abstrakt: Ak $f$ je reálna funkcia reálnej premennej a $r$ je z intervalu $[0,1)$, definujeme $P_r(f)$ ako množinu tých $x$, pre ktoré existuje množina $A$ obsahujúca $x$ taká, že pórovitosť jej doplnku v $x$ je väčšia než $r$ a taká, že zúženie $f$ na množinu $A$ je spojité v $x$. Podobne definujeme $M_r(f)$, akurát žiadame, aby pórovitosť doplnku bola väčšia alebo rovná než $r$. Ďalej definujeme $S_r(f)$ ako množinu tých $x$, že pre každé kladné epsilon existuje množina $A$ obsahujúca $x$ taká, že jej doplnok má v bode $x$ pórovitosť väčšiu než $r$ a taká, že $f(A)$ leží v intervale $(f(x)-\varepsilon, f(x)+\varepsilon)$. Podobne definujeme $N_r(f)$, ibaže namiesto $\gt$ ziadame $\ge$. V prednáške podáme úplnú charakterizáciu množín $P_r(f)$, $S_r(f)$, $M_r(f)$ a $N_r(f)$.

9. 2. 2017 – RNDr. Peter Eliaš, PhD. – Uzavreté systémy množín a funkcií vzhľadom ku Galoisovej konexii určenej rovnomernou aproximovateľnosťou

Abstrakt: Nech $C(X,Y)$ označuje metrický priestor spojitých zobrazení z topologického priestoru $X$ do metrického priestoru $Y$, so supremovou metrikou. Nech $Cl(X)$ označuje systém všetkých uzavretých podmnožín priestoru $X$. Ak $\Phi\subseteq C(X,Y)$, uvažujme Galoisovu konexiu medzi podsystémami $C(X,Y)$ a podsystémami $Cl(X)$, určenú reláciou $(f,E)\in R$ $\Leftrightarrow$ existuje postupnosť navzájom rôznych funkcií z $\Phi$, rovnomerne konvergujúca k funkcii $f$ na množine $E$. Systémy funkcií a množín, uzavreté vzhľadom na zodpovedajúce uzáverové operátory, tvoria úplný zväz. V prípade, že $\Phi$ je množina všetkých konštantných funkcií, resp. lineárnych funkcií bez absolútneho člena, je príslušný zväz izomorfný zväzu všetkých rozkladov priamky (resp. priamky bez jedného bodu) na uzavreté množiny, a každý prvok zväzu je generovaný konečnou alebo spočítateľnou množinou funkcií.

23. 2. 2017 – doc. RNDr. Roman Frič, DrSc. – Nezávislosť

odkaz na prezentáciu

16. 3. 2017 – RNDr. Emília Halušková, CSc. – Vlastnosť EKP pre monounárne algebry

Abstrakt: Hovoríme, že algebra $A$ má vlastnosť EKP, ak ku každej kongruencii $r$ algebry $A$ existuje endomorfizmus algebry $A$, ktorého jadrom je kongruencia $r$. Pre monounárne algebry s injektívnou operáciou, konečné monounárne algebry a dve podtriedy triedy všetkých súvislých monounárnych algebier sme popísali všetky monounárne algebry s vlastnosťou EKP. Ďalej sme ukázali, že každá monounárna algebra s EKP má zaujímavé podalgebry, ktoré majú EKP. (odkaz na prezentáciu)

30. 3. 2017 – Mgr. Ivana Krajňáková – Štvorec na deterministických, alternujúcich a booleovských automatoch

Abstrakt: Venujeme sa operácii štvorec na deterministických, alternujúcich a booleovských konečnostavových automatoch. Preskúmame zložitosť štvorca jazykov akceptovaných n-stavovými deterministickými automatmi s k koncovými stavmi. Pre každé takéto $n$ a $k$ popíšeme binárny jazyk taký, že minimálny deterministický automat pre jeho štvorec má $(n − k) 2^n + k · 2^{n−1}$ stavov.

Osobitne sa sústredime na jazyky reprezentovaných deterministickými automatmi, kde iba jeden stav je nekoncový. Využitím nášho jazyka, ktorý je ťažký pre štvorec na deterministických automatoch definujeme taký binárny jazyk akceptovaný $n$-stavovým alternujúcim automatom, že každý alternujúci automat pre jeho štvorec má aspoň $2^n +n+ 1$ stavov. Zovšeobecnením tohto nášho výsledku ukážeme tesnosť horného odhadu $2^m + n + 1$ pre zložitosť zreťazenia jazykov reprezentovaných alternujúcimi automatmi s $m$ a $n$ stavmi. Týmto vyriešime otvorený problém stavovej zložitosti zreťazenia, ktorý formulovali Fellah, Jürgensen, Yu [1990, Internat. J. Computer Math. 35, 117–132]. (odkaz na prezentáciu)

20. 4. 2017 – Mgr. Michal Hospodár – On the Magic Number Problem of the Cut Operation

Abstract: We investigate the state complexity of languages resulting from the cut operation of two regular languages represented by deterministic finite automata with $m$ and $n$ states, respectively. We study the magic number problem of the cut operation and show that the entire range of complexities, up to the known upper bound, can be produced in case of binary alphabets. Moreover, we prove that in the unary case only complexities up to $2m-1$ and between $n$ and $m+n-2$ can be produced, while complexities within the interval $2m$ up to $n-1$ cannot be reached—these non-producible numbers are called “magic.”