Seminár detašovaného pracoviska Matematického ústavu SAV v Košiciach
| 24. 1. 2014 | Shinnosuke Seki (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 the presentation) |
|
| 4. 2. 2014 | Ján Borsík – 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 | Peter Eliaš – 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ú:
|
|
| 13. 3. 2014 | Roman Frič – 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 | 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 | Ján Haluška – 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 | Emília Halušková – 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
|
|
| 19. 9. 2014 | Galina Jirásková – 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 | Peter Mlynárčik – Complement on Prefix-Free, Suffix-Free, and Non-Returning NFA Languages |
| Abstract: 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 | Matúš Palmovský – Kleene Closure on Regular Languages, Prefix-Free and Prefix-Closed regular languages |
| Abstract:
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 | Miroslav Ploščica – Congruence lattices of algebras (odkaz na prezentáciu) |
| 21. 11. 2014 | Miroslav Repický – 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. |