Seminár detašovaného pracoviska Matematického ústavu SAV v Košiciach
21. 1. 2016 | Ján Borsík – Body konvergencie a rovnomernej konvergencie |
Abstrakt: Nech $f_n$ sú funkcie definované na topologickom priestore $X$ s hodnotami v metrickom priestore $Y$. Hovoríme, že postupnosť $(f_n)$ konverguje rovnomerne v bode $x$, ak ku každému $\varepsilon>0$ existuje index $n_0$ a okolie $U$ tohto bodu, že pre každé $y\in U$ a pre každé $m,n>n_0$ je vzdialenosť bodov $f_m(y)$ a $f_n(y)$ menšia než $\varepsilon$. T. Šalát ukázal, že množina bodov rovnomernej konvergencie je typu $G_\delta$ (a ak postupnosť je konvergentná, tak obsahuje všetky izolované body). Ukážeme, že ak $X$ je metrický priestor, potom každá množina typu $G_\delta$ obsahujúca všetky izolované body je množinou bodov rovnomernej konvergencie nejakej konvergentnej postupnosti, a tiež nejakej postupnosti kvázispojitých funkcií. Ale už nemusí byť množinou bodov rovnomernej konvergencie nejakej konvergentnej postupnosti kvázispojitých funkcií. | |
16. 2. 2016 | Peter Eliaš – O jednom kombinatorickom probléme |
Abstrakt:
Pre zadané $n$ hľadáme čo najväčšie $m$ také, že existuje systém $\{(X_i,Y_i):i=1,\dots,m\}$
spĺňajúci podmienky
|
|
1. 3. 2016 | Roman Frič – Upgrading probability (odkaz na prezentáciu ) |
18. 3. 2016 | Emília Halušková – O triedach algebier uzavretých na direktné limity |
Abstrakt:
Nech $F$ je typ algebier a $L_F$ je trieda všetkých logických formúl nad $F$.
Ak $\Sigma$ je množina viet z $L_F$, tak $\Sigma^*$ označuje triedu všetkých algebier
typu $F$, v ktorých platí každá veta zo $\Sigma$. Nech $n$ je prirodzené číslo a $\kappa$ je ordinálne číslo. Nech $\mathbf{A}$, $\mathbf{B}$ sú formuly z $L_F$ bez kvantifikátorov také, že $x_0,\dots,x_{n-1}$ sú všetky premenné formuly $\mathbf{A}$ a $x_t$, $t\lt\kappa$, sú všetky premenné formuly $\mathbf{B}$. Uvažujme vetu $\Phi$ danú predpisom
$(\forall x_0,\dots,x_{n-1})$
$(\mathbf{A}(x_0,\dots,x_{n-1})$ $\Rightarrow$ $(\exists x_t,$ $n\le t\lt\kappa)$
$\mathbf{B}(x_t,$ $t\lt\kappa))$.
Ak vo $\Phi$ je formula $\mathbf{A}$ konečná a $\mathbf{B}$ kladná, tak trieda algebier $\{\Phi\}^*$ je uzavretá na direktné limity. Pre monounárne algebry platí tvrdenie bez predpokladu, že $\mathbf{A}$ je konečná. Ďalej bola prezentovaná nasledujúca veta: Veta. Nech $\Sigma$ je množina viet prvého rádu z $L_F$. Potom je ekvivalentné:
|
|
1. 4. 2016 | Ján Haluška – Polarity vo vnímaní farieb |
22. 4. 2016 | Giselle Antunes Monteiro – Kurzweil's and Dobrakov's approaches to integration (odkaz na prezentáciu ) |
6. 5. 2016 | Ing. Michal Hospodár – Stavová zložitosť konkatenácie regulárnych jazykov |
Abstract: We study the state complexity of the concatenation operation on regular languages represented by deterministic and alternating finite automata. For deterministic automata, we show that the upper bound $m2^n-k2^{n-1}$ on the state complexity of concatenation can be met by ternary languages, the first of which is accepted by an $m$-state DFA with $k$ final states, and the second one by an $n$-state DFA with $\ell$ final states for arbitrary integers $m,n,k,\ell$. In the case of $k\le m-2$, that is, in the case when the first automaton has at least two non-final states, we are able to provide appropriate binary witnesses. We use these witnesses to describe a pair of binary languages meeting the upper bound $2^m+n+1$ for the concatenation on alternating finite automata. This solves an open problem stated by Fellah, J\"urgensen, and Yu [1990, Constructions for alternating finite automata, Intern. J. Computer Math. 35, 117-132], where the upper bound $2^m+n+1$ is proven. | |
26. 5. 2016 | Tomáš Gregor – Polopole hyperbolických komutatívnych kvaterniónov |
Abstrakt: Systém $(S,+,\cdot)$ nazývame polopole, ak $+$ je komutatívna asociatívna operácia s neutrálnym prvkom $0$, $(S\setminus \{0\},\cdot)$ je komutatívna grupa a platí distributívny zákon $x\cdot (y+z) = x \cdot y + x\cdot z$ $\forall x,y,z \in S$. Hyperbolické komutatívne kvaternióny sú čísla tvaru $a+b i+c j+d k$, kde $a,b,c,d \in \mathbb{R}$ a $i,j,k$ sú imaginárne jednotky. Sčítanie je definované po zložkách a násobenie je dané vzťahom $i^2=j^2=k^2= ijk=1$. Tento systém obsahuje delitele nuly, ale existuje v ňom podmnožina, ktorá je polopoľom. | |
16. 6. 2016 | Peter Mlynárčik – Nondeterministic Complexity of Operations on Closed and Ideal Languages |
Abstract: We study the nondeterministic state complexity of basic regular operations on the classes of prefix-, suffix-, factor-, and subword-closed regular languages and on the classes of right, left, two-sided, and all-sided ideal regular languages. For the operations of union, intersection, complementation, concatenation, square, star, and reversal, we get the tight upper bounds for all considered classes. | |
13. 9. 2016 | Galina Jirásková – Operations on Unambiguous Finite Automata (odkaz na prezentáciu ) |
23. 9. 2016 | Markus Holzer (Justus-Liebig-Universität, Giessen, Germany) – The Computational Complexity of RaceTrack |
Abstract: Martin Gardner in the early 1970’s described the game of RaceTrack [M. Gardner, Mathematical games—Sim, Chomp and Race Track: new games for the intellect (and not for Lady Luck), Scientific American, 228(1):108–115, Jan. 1973]. Here we study the complexity of deciding whether a RaceTrack player has a winning strategy. We first prove that the complexity of RaceTrack reachability, i.e., whether the finish line can be reached or not, crucially depends on whether the car can touch the edge of the carriageway (racetrack): the non-touching variant is NL-complete while the touching variant is equivalent to the undirected grid graph reachability problem, a problem in L but not known to be L-hard. Then we show that single-player RaceTrack is NL-complete, regardless of whether driving on the track boundary is allowed or not, and that deciding the existence of a winning strategy in Gardner’s original two-player game is P-complete. Hence RaceTrack is an example of a game that is interesting to play despite the fact that deciding the existence of a winning strategy is most likely not NP-hard. This is a joint work with Pierre McKenzie from the University de Montreal, Quebec, Canada. | |
27. 9. 2016 | Matúš Palmovský – State complexity of combined operations for prefix-free a suffix-free languages |
Abstract: We investigate the state complexity of combined operations for prefix-free and suffix-free regular languages. Prefix-free and suffix-free deterministic finite-state automata have a unique structural property that is crucial for obtaining the precise state complexity of basic operations. Based on the same property, we establish the state complexity of several operations: catenation-of-union, catenation-of-intersection, catenation-of-star. | |
13. 10. 2016 | Miroslav Ploščica – Voľné množiny pre systémy množín funkcií |
27. 10. 2016 | Jozef Pócs – On concept reduction based on some graph properties |
Abstract: The theory of concept lattices represents a well established and widely used conceptual data-mining method. Considering additional information represented by a graph structure on a set of objects, we propose a reduction of concepts. Using graph-theoretical point of view on FCA together with simple probabilistic arguments we derive the mean value of the cardinality of the reduced hierarchical structure. | |
24. 11. 2016 | Miroslav Repický – Umocňovanie mohutností v modeli Helperna a Lévyho |
Abstrakt:
Nech $A$ je generická spočítateľná množina Cohenových reálnych čísel pridaná
forcingom s konečnými funkciami z $\omega\times\omega$ do $2$ a nech
$\mathfrak{N}$ je tranzitívny model ZF tvorený dedične ordinálne definovateľnými
množinami nad $A$ vo $V[G]$.
V modeli $\mathfrak{N}$ neplatí axióma výberu a každý ideál na Booleovej algebre
sa dá rozšíriť na prvoideál.
Pre mohutnosť množiny (kardinálne číslo) $\mathfrak{m}=|X|$ označme mohutnosti
$e(\mathfrak{m})=|[X]^{\lt\omega}|$,
$e^*(\mathfrak{m})=|\bigcup_{n\in\omega}[X]^n\times n!|$,
a tiež $\mathfrak{a}=|A|$. Mohutnosti $\mathfrak{a}\lt e(\mathfrak{a})\lt e^*(\mathfrak{a})$ sú Dedekindovsky konečné v modeli $\mathfrak{N}$ a pre umocňovanie mohutností v modeli $\mathfrak{N}$ platí:
|