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

···   2020-21   •   2022   •   2023   •   2024
21. 3. 2024 Miroslav Repický
11. 1. 2024 Michal Hospodár – Operational complexity in subregular classes
Abstract: The state complexity of a regular operation is a function that assigns the maximal state complexity of the language resulting from the operation to the sizes of deterministic finite automata recognizing the operands of the operation. We study the state complexity of intersection, union, concatenation, star, and reversal on the classes of combinational, singleton, finitely generated left ideal, symmetric definite, star, comet, two-sided comet, ordered, star-free, and power-separating languages. We get the exact state complexities in all cases. The complexity of all operations on combinational languages is given by a constant function. The state complexity of the considered operations on singleton languages is $\min\{m,n\}$, $m+n-3$, $m+n-2$, $n-1$, and $n$, respectively, and on finitely generated left ideals, it is $mn-2$, $mn-2$, $m+n-1$, $n+1$, and $2^{n-2} + 2$. The state complexity of concatenation, star, and reversal is $m2^n -2^{n-1} -m+1$, $n$, $2^n$ and $m2^{n-1} -2^{n-2} +1$, $n+1$, $2^{n-1} +1$ for star and symmetric definite languages, respectively. We also show that the complexity of reversal on ordered and power-separating languages is $2^{n} -1$, which proves that the lower bound for star-free languages given by [Brzozowski, Liu, Int. J. Found. Comput. Sci. 23, 1261-1276, 2012] is tight. In all the remaining cases, the complexity is the same as for regular languages. Except for reversal on finitely generated left ideals and ordered languages, all our witnesses are described over a fixed alphabet.
25. 1. 2024 Galina Jirásková – Operational complexity: NFA-to-DFA trade-off
Abstract: We examine operational complexity assuming that the arguments are given as nondeterministic finite automata and the resulting language is represented by a deterministic finite automaton. We show that the known upper bounds for Boolean operations and concatenation are met by ternary languages, and we prove that they are asymptotically tight in the binary case. For the cut and square operations, we get tight upper bounds $2^{m-1}(2^n+1)$ and $\frac{3}{4}2^{2n}$, respectively. Our witnesses are described over a four-letter alphabet for cut, and a ten-letter alphabet for square. We also show that the tight upper bound on the syntactic complexity of a language given by an n-state NFA is $2^{n^2}$. For the square root operation, we provide a lower bound $2^{n^2-n}$ and an upper bound $2^{n^2}$.
22. 2. 2024 Jozef Pócs – On zerodivisor graphs of infinite posets
Abstract: It is known that the so-called Beck’s conjecture, i.e. the equality of the finite clique and chromatic numbers of a zerodivisor graph, holds for partially ordered sets. A simple direct proof of this fact will be given. Also the case when the finiteness assumption of the clique number is omitted is investigated. It is shown that in this case the conjecture fails in general and some counterexamples will be presented.