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

<<  2016  >>

21. 1. 2016 – doc. RNDr. Ján Borsík, CSc. – 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 – RNDr. Peter Eliaš, PhD. – 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

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 – doc. RNDr. Roman Frič, DrSc. – Upgrading probability

link to presentation

18. 3. 2016 – RNDr. Emília Halušková, CSc. – 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. $\Sigma^*$ je uzavretá na direktné limity,
  2. existuje množina $\Delta$ viet prvého rádu, ktoré sú priesekmi formúl tvaru formuly $\Phi$, taká, že $\Sigma^*=\Delta^*$.

1. 4. 2016 – doc. RNDr. Ján Haluška, CSc. – Polarity vo vnímaní farieb

22. 4. 2016 – Giselle Antunes Monteiro – Kurzweil's and Dobrakov's approaches to integration

link to presentation

6. 5. 2016 – Mgr. Michal Hospodár – Stavová zložitosť konkatenácie regulárnych jazykov

26. 5. 2016 – Mgr. 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 – Mgr. 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 – RNDr. Galina Jirásková, CSc. – Operations on Unambiguous Finite Automata

link to presentation

23. 9. 2016 – prof. Markus Holzer (Justus-Liebig-Universität, Giessen, Germany) – The Computational Complexity of RaceTrack – Drive Hard, Brake Late, Go Fast

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 – Mgr. 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 – doc. RNDr. Miroslav Ploščica, CSc. – Voľné množiny pre systémy množín funkcií

27. 10. 2016 – RNDr. Jozef Pócs, PhD. – 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 – doc. RNDr. Miroslav Repický, CSc. – 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í:

To isté platí aj v $L(A)$ (model Halperna a Lévyho).