Mathematical Institute of the Slovak Academy of Sciences, extension in Košice SK  EN 
About us
Activity
Research
Education

Seminar of the Extension of the Mathematical Institute SAS in Košice

···   2013   •   2014   •   2015   •   2016   •   2017   •   2018   •   2019   ···
 
21. 1. 2016 Ján Borsík – Points of convergence and of uniform convergence
Abstract: Let $f_n$ be functions defined on a topological space $X$ with values in a metric space $Y$. We say that a sequence $(f_n)$ converges uniformly at a point $x$ if for any $\varepsilon>0$ there exists an index $n_0$ and a neigbourhood $U$ of $x$ such that for every $y\in U$ and every $m,n>n_0$, the distance of points $f_m(y)$ and $f_n(y)$ is less than $\varepsilon$. T. Šalát proved that the set of points of uniform convergence is a $G_\delta$-set (and if the sequence converges then it contains all isolated points). We show that if $X$ is a metric space then every $G_\delta$-set containing all isolated points is a set of points of uniform convergence for some convergent sequence, and also of some sequence of quasicontinuous functions. Nevertheless it need not to be a set of points of uniform convergence of some convergent sequence of quasicontinuous functions.
16. 2. 2016 Peter Eliaš – On one combinatorial problem
Abstract: For given $n$ we are looking for the greatest possible $m$ such that there exists a family $\{(X_i,Y_i):i=1,\dots,m\}$ satisfying conditions
  • for every $i$, $X_i\cap Y_i=\emptyset$ and $X_i\cup Y_i\subseteq\{1,\dots,n\}$,
  • for every $i\neq j$, $|X_i\cap Y_j|\le 1$,
  • for every $i\neq j$, $|X_i\cap Y_j|=1$ or $|X_j\cap Y_i|=1$.
We show that the existence of such family is equivalent to the existence of a tournament with $m$ vertices, whose edges is possible to cover by edges of $n$ disjoint directed bicliques (i.e., directed graphs consisting of two disjoint vertex sets and all edges from the first set the second one). Using ranks of graph matrices we show that $m_{max}\le n+\binom{n}{2}+1$, while our conjecture is $m_{max}\le 2n$. In the proof we need to find a lower bound for ranks matrices of a certain form.
1. 3. 2016 Roman Frič – Upgrading probability (link to the presentation )
18. 3. 2016 Emília Halušková – On direct limit closed classes of algebras
Abstract: Let $F$ be a type of algebras and $L_F$ be the family of all logic formulas over $F$. If $\Sigma$ is a set of sentences from $L_F$ then let $\Sigma^*$ denote the family of all algebras of type $F$ satisfying all sentences from $\Sigma$.
Let $n$ be a natural number and le $\kappa$ be an ordinal. Let $\mathbf{A}$, $\mathbf{B}$ be quantifier-free formulas from $L_F$ such that $x_0,\dots,x_{n-1}$ are all variables occuring in the formula $\mathbf{A}$ and $x_t$, $t\lt\kappa$, are all variables occuring in the formula $\mathbf{B}$. Let us consider the sentence $\Phi$ given by
$(\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))$.

If the formula $\mathbf{A}$ is finite a $\mathbf{B}$ is positive in $\Phi$ then the family of algebras $\{\Phi\}^*$ je closed under direct limits. For monounary algebras, the statement holds without assuming that $\mathbf{A}$ is finite.
The following theorem was also presented:
Theorem. Let $\Sigma$ be a set of first order sentences from $L_F$. The the following statements are equivalent:
  1. $\Sigma^*$ is closed under direct limits,
  2. there exists a set $\Delta$ of first order sentences which are meets of formulas having the form of the formula $\Phi$, and such that $\Sigma^*=\Delta^*$.
1. 4. 2016 Ján Haluška – Polarities in the perception of colours
22. 4. 2016 Giselle Antunes Monteiro – Kurzweil's and Dobrakov's approaches to integration (link to the presentation )
6. 5. 2016 Ing. Michal Hospodár – Stavová zložitosť konkatenácie regulárnych jazykov
Abstrakt: 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 (link to the presentation )
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).