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

··· 2013 • 2014 • 2015 • 2016 • 2017 • 2018 • 2019 ···

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 pre každé $i$, $X_i\cap Y_i=\emptyset$ a $X_i\cup Y_i\subseteq\{1,\dots,n\}$, pre každé $i\neq j$, $\|X_i\cap Y_j\|\le 1$, pre každé $i\neq j$, $\|X_i\cap Y_j\|=1$ alebo $\|X_j\cap Y_i\|=1$. Ukážeme, že existencia takého systému je ekvivalentná s existenciou turnaja s $m$ vrcholmi, ktorého hrany je možné pokryť hranami $n$ disjunktných orientovaných biklík (orientovaných grafov tvorených dvoma disjunktnými množinami vrcholov a všetkými hranami vedúcimi z prvej množiny do druhej). Použitím hodností grafových matíc ukážeme, že $m_{max}\le n+\binom{n}{2}+1$, pričom hypotézou je $m_{max}\le 2n$. K dôkazu potrebujeme nájsť dolné ohraničenie pre hodnosti matíc istého tvaru.
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é: $\Sigma^$ je uzavretá na direktné limity, existuje množina $\Delta$ viet prvého rádu, ktoré sú priesekmi formúl tvaru formuly $\Phi$, taká, že $\Sigma^=\Delta^*$.
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í: $2^\mathfrak{m}= 2^\mathfrak{m}\cdot2^{\aleph_0}= (2^\mathfrak{m})^{\aleph_0}$ a $2^{e(\mathfrak{m})}=2^{e^(\mathfrak{m})}$ pre každú nekonečnú mohutnosť $\mathfrak{m}$, $2^\mathfrak{m}=2^{e(\mathfrak{m})}= 2^{e^(\mathfrak{m})}= \mathfrak{m}^\mathfrak{m}=2^{\aleph_0}$ pre každú nekonečnú Dedekindovsky konečnú mohutnosť $\mathfrak{m}$, $2^\mathfrak{a}=2^{e(\mathfrak{a})}= 2^{e^*(\mathfrak{a})}= \mathfrak{a}^\mathfrak{a}=2^{\aleph_0}$. To isté platí aj v $L(A)$ (model Halperna a Lévyho).