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

<<  2014  >>

24. 1. 2014 – Shinnosuke Seki, PhD. (Aalto University, Finland) – A stronger square conjecture on binary words

Abstract: A square is a word of the form $xx$. Examples of square include $aa$, $abaaba$, and $aabaaabaabaaab$. Repetitions in general are useful structures in algorithms to handle words such as data-compression algorithms. A problem of interest asks how many distinct squares can be found on a given word of length $n$. By distinct, we mean that no matter how many times the same square occur, the count is just 1. We can easily prove that $n(n-1)/4$ is an upper bound, but Fraenkel and Simpson improved the bound up to $2n$. In contrast, the conjectured upper bound is $n$. We propose a tighter bound $(2k-1)/(2k+2)\cdot n$ for words over binary alphabet $\{a, b\}$, where $k$ is the number of $b$'s, and a novel approach towards it. Square-densest words are strongly believed to be binary. For various words that are likely to be square-densest, we take the approach and prove that the tighter bound holds for them. (link to presentation)

4. 2. 2014 – doc. RNDr. Ján Borsík, CSc. – Silne kvázispojité funkcie vzhľadom na pórovitosť

Abstrakt: Je známe, že kvázispojité funkcie nemusia byt merateľné. Množina bodov nespojitosti kvázispojitej funkcie je síce prvej kategórie, ale nemusí byť miery nula. Pre každé $r\in [0,1)$ definujeme triedy funkcií $P_r$ a $S_r$: Funkcia $f$ je z triedy $P_r$ ak pre každé $x$ existuje množina $A$ obsahujúca $x$ taká, že pórovitosť tejto množiny v bode $x$ je väčšia než $r$ a zúženie funkcie $f$ na $A$ je spojité v $x$. Funkcia $f$ je z triedy $S_r$, ak pre každé $x$ a každé kladné $\varepsilon$ existuje množina $A$ obsahujúca $x$ taká, že pórovitosť $A$ v $x$ je väčšia než $r$ a $|f(x)-f(y)|<\varepsilon$ pre $y\in A$. Ukážeme, že všetky tieto triedy funkcií sú merateľné, ležia medzi spojitými a kvázispojitými funkciami, sú navzájom rôzne a pre všetky je množina bodov nespojitosti $\sigma$-pórovitá.

27. 2. 2014 – RNDr. Peter Eliaš, PhD. – Medzi Dirichletovými a Kroneckerovými množinami

Abstrakt: Pre $n\in\mathbb{Z}$, označme $\chi_n:\mathbb{T}\to\mathbb{T}$ funkciu $\chi_n(x)=nx$, kde $\mathbb{T}$ je faktorová topologická grupa $\mathbb{R}/\mathbb{Z}$. Množina $X\subseteq\mathbb{T}$ sa nazýva Dirichletova množina, ak postupnosť funkcií $\chi_{n_k}$ rovnomerne konverguje k nulovej funkcii na $X$, pre nejakú rastúcu postupnosť $\{n_k\}_{k\in\mathbb{N}}$. Množina $X$ sa nazýva Kroneckerova množina, ak pre ľubovoľnú spojitú funkciu $f:\mathbb{T}\to\mathbb{T}$ existuje rastúca postupnosť $\{n_k\}_{k\in\mathbb{N}}$ taká, že postupnosť funkcií $\chi_{n_k}$ rovnomerne konverguje k $f$ na $X$.

Nech $C(\mathbb{T},\mathbb{T})$ je systém všetkých spojitých funkcií z $\mathbb{T}$ do $\mathbb{T}$ a $K(\mathbb{T})$ je systém všetkých uzavretých podmnožín $\mathbb{T}$. Pre $\mathcal{F}\subseteq C(\mathbb{T},\mathbb{T})$ označme $K(\mathcal{F})=\{X\in K(\mathbb{T}):(\forall f\in\mathcal{F}) (\exists\,$rastúca$\,\{n_k\}_{k\in\mathbb{N}})\,\chi_{n_k}\rightrightarrows f\,$na$\,X\}$. Podobne, pre $K\subseteq K(\mathbb{T})$ označme $\mathcal{K}(K)=\{f\in C(\mathbb{T},\mathbb{T}):(\forall X\in K) (\exists\,$rastúca$\,\{n_k\}_{k\in\mathbb{N}})\,\chi_{n_k}\rightrightarrows f\,$na$\,X\}$. Zobrazenia $K:\mathcal{P}(C(\mathbb{T},\mathbb{T}))\to\mathcal{P}(K(\mathbb{T}))$ a $\mathcal{K}:\mathcal{P}(K(\mathbb{T}))\to\mathcal{P}(C(\mathbb{T},\mathbb{T}))$ tvoria Galoisovu-Tukeyho konexiu.

Problém: Ktoré dvojice $K\subseteq K(\mathbb{T})$, $\mathcal{F}\subseteq C(\mathbb{T},\mathbb{T})$ tvoria stabilný systém, t. j. $\mathcal{F}=\mathcal{K}(K)$ a $K=K(\mathcal{F})$?

Príkladmi sú:

Ukazuje sa, že s každým stabilným systémom je spojená nejaká forma lineárnej nezávislosti na $\mathbb{T}$.

13. 3. 2014 – doc. RNDr. Roman Frič, DrSc. – Poznámky o epireflexii

Abstrakt: V rôznych oblastiach matematiky sa s výhodou využíva možnosť nahradiť určitý matematický objekt $A$ vhodným objektom $A^*$, pričom $A$ aj $A^*$ majú rovnaké základné vlastnosti, sú teda v tomto kontexte rovnocenné, ale $A^*$ ma dodatočné iné dobré vlastnosti. Napríklad, racionálne čísla rovnocenne nahradia reálne čísla pri bežnom počítaní, ale v matematickej analýze potrebujeme existenciu suprema a infima, preto racionálne čísla nahradíme reálnymi číslami. Podobne, pri niektorých topologických konštrukciách metrický priestor $X$ potrebujeme nahradiť jeho metrickým zúplnením $X^*$. Poznamenajme, že $X$ je hustým podpriestorom $X^*$, pričom $X$ a $X^*$ „majú rovnaké“ rovnomerne spojité funkcie. Ešte abstraktnejší je prechod od úplne regulárneho topologickeho priestoru $X$ ku jeho Čechovej-Stoneovej kompaktifikácii $\beta X$. Pritom $X$ je hustý podpriestor $\beta X$, $X$ a $\beta X$ „majú rovnaké“ spojité ohraničené funkcie a $\beta X$ je najväčší zo všetkých úplne regulárnych priestorov s týmito dvomi vlastnosťami. Je to aj najväčšia zo všetkých kompaktifikácii (každú inú dostaneme ako vhodný kvocient $\beta X$, t. j. zlepením niektorých ideálnych bodov).

Ja som sa v minulosti zaoberal konštrukciami, vlastnosťami a aplikáciami podobných dvojíc objektov. V teórii kategórií sa príslušný „vylepšený“ objekt nazýva epireflexiou pôvodného. Ukazuje sa, že vo fuzzy teórii pravdepodobnosti možno za epireflexiu považovať prechod od systému jednoduchých náhodných udalostí ku systému všetkých náhodných udalostí, pričom pravdepodobnostné miery na oboch systémoch „sú rovnaké“.

10. 4. 2014 – Mgr. Tomáš Gregor – Kalkulus v tri-polárnych komplexných číslach

Abstrakt: Komplexné čísla možno chápať ako triedy ekvivalencie $n$-tíc nezáporných reálnych čísel, kde reláciou ekvivalencie je tzv. „cancellation law“. Budeme uvažovať $n=3$ a množinu tried ekvivalencie označíme $\mathbb{C}_3$. Definujeme deriváciu funkcie $f: U \to \mathbb{C}_3$, kde $U\subseteq \mathbb{C}_3$, a ukážeme ekvivalentnú podmienku diferencovateľnosti, ktorá je analógiou Cauchyho-Riemannovej podmienky diferencovateľnosti v klasickom modeli komplexných čísel. Ďalej zavedieme krivkový integrál z funkcie $f$ pozdĺž krivky $\gamma: [a,b]\subseteq \mathbb{R} \to \mathbb{C}_3$. Ukážeme, že za istých predpokladov krivkový integrál nezávisí od výberu krivky spájajúcej dané dva body v $\mathbb{C}_3$; v takom prípade platí analógia Newtonovho-Leibnizovho vzorca. Otázkou zostáva zavedenie miery na $\mathbb{C}_3$ a integrálu z funkcie $f: U \to \mathbb{C}_3$.

22. 5. 2014 – doc. RNDr. Ján Haluška, CSc. – Aplikácie multipolárnych priestorov

Abstrakt: Uvažujeme o možných aplikáciách multipolárnych vektorových priestorov v teórii elektromagnetického poľa, vnímania farieb a vnímania zvukov a hudby.

5. 6. 2014 – RNDr. Emília Halušková, CSc. – Monounárne algebry s jednoduchými direktnými limitami

Abstrakt: Algebru A nazývame algebrou s jednoduchými direktnými limitami, ak každá algebra získaná konštrukciou direktnej limity z algebry A je retraktom A. Je známe, že konečné algebry sú algebrami s jednoduchými direktnými limitami. Ďalej sú známe príklady nekonečných algebier s touto vlastnosťou.

Veta. Nech $A$ je monounárna algebra s operáciou $f$. Ak $A$ je algebra s jednoduchými direktnými limitami, tak

  1. v grafe algebry $A$ do každého vrcholu vchádza nanajvýš konečný počet hrán,
  2. algebra $A$ obsahuje nanajvýš konečný počet cyklov rovnakej dĺžky,
  3. algebra $A$ obsahuje nanajvýš konečný počet necyklických komponentov,
  4. pre každý komponent $K$ algebry $A$ existuje $B\subseteq K$ taká, že $B$ je podalgebra $A$ a $f\vert B$ je bijekcia.

Ak $f$ je bijekcia, tak je ekvivalentné

  1. $A$ je algebra s jednoduchými direktnými limitami,
  2. platí 1., 2.

Z tejto vety vyplýva, že monounárna algebra s jednoduchými direktnými limitami má nanajvýš spočítateľne veľa komponentov a jej mohutnosť je menšia alebo rovná mohutnosti kontinua. Pritom existujú monounárne algebry s jednoduchými direktnými limitami, ktoré majú spočítateľne veľa komponentov a zároveň ich mohutnosť je rovná mohutnosti kontinua.

19. 9. 2014 – RNDr. Galina Jirásková, CSc. – Alternujúce a booleovské konečné automaty

Abstrakt: Ukazujeme, že $2^n+1$ stavov stačí a aj je treba v najhoršom prípade na simuláciu alternujúceho $n$-stavového konečného automatu pomocou nedeterministického automatu (s jedným počiatočným stavom). Zároveň skúmame zložitosť operácií na jazykoch reprezentovaných alternujúcimi a booleovskými automatmi.

3. 10. 2014 – Mgr. Peter Mlynárčik – Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages

Abstrakt: We were dealing with the nondeterministic state complexity in case of complementation on prefix-free, suffix-free and non-returning languages. We sketched the proofs that the tight bound in case of prefix-free and suffix-free languages is $2^{n-1}$ over a ternary alphabet and mentioned that this bound cannot be met by any binary prefix-free language. On non-returning languages, the upper bound is $2^{n-1}+1$, and it is tight already in the binary case. We also showed that nondeterministic state complexity of complement of prefix-free and suffix-free languages in the unary case is in $\Theta(\sqrt n)$ class, but in case of non-returning languages it remains exponential.

24. 10. 2014 – Mgr. Matúš Palmovský – Kleene Closure on Regular Languages, Prefix-Free and Prefix-Closed regular languages

Abstrakt: We study the Kleene closure operation on regular and prefix-free languages. Using an alphabet of size $2n$, we get the contiguous range from ${1}^{}$ to ${3/4\cdot 2^n}^{}$ of complexities of the Kleene closure of regular languages accepted by minimal $n$-state deterministic finite automata. In the case of prefix-free languages, the Kleene closure may attain just three possible complexities $n-2$, $n-1$, and $n$.

Next we investigate the complexity of basic regular operations on languages represented by incomplete deterministic or nondeterministic automata, in which all states are final. Such languages are known to be prefix-closed. We get tight bounds on both incomplete and nondeterministic state complexity of star on prefix-closed languages.

7. 11. 2014 – doc. RNDr. Miroslav Ploščica, CSc. – Congruence lattices of algebras

link to presentation

21. 11. 2014 – doc. RNDr. Miroslav Repický, CSc. – Množiny symetrickej spojitosti

Abstrakt: V prednáške boli prezentované výsledky o množinách symmetrickej spojitosti reálnych funkcií nadväzujúce na práce Frieda, Belnu a Darjiho.