Seminar of the Extension of the Mathematical Institute SAS in Košice
| next: | |
| 12. 12. 2024, 9:00 | Ivan Vlček – On aggregation of (only) partially ordered vectors |
|
Abstract:
In an attempt to obtain aggregated outputs applicable in fields such as multicriteria decision making, experts' evaluation criteria,
deep learning or fuzzy systems, different problems arise. These include the selection of appropriate aggregation function,
fusing different types of information structures, choosing suitable arrangement of multivalued structures.
As a suitable tool to fuse data Choquet integrals can be used. In [1], authors suggested how the notion can be applied in situations
when all input vectors need not to be comparable. Our goal is to present their main ideas and results.
Bibliography [1] Ferrero-Jaurrieta M., Horanská Ľ., Lafuente J., Mesiar R., Dimuro G.P., Takáč Z., Goméz M., Fernández J., Bustince H., Degree of totalness: How to choose the best admissible permutation for vector fuzzy integration. Fuzzy Sets and Systems 466 (2023) 108461. |
| previous: | |
| 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. | |
| 21. 3. 2024 | Miroslav Repický – Capacties on $\omega$ |
| Abstract: We examine the concept of capacity on $\omega$ and capacitous ideals. We deal with sequences of capacities and the question of which $F_{\sigma\delta}$ ideals are determined by sequences of capacities. | |
| 18. 4. 2024 | Peter Eliaš – The construction of the free orthomodular poset over a given orthoposet, II |
|
Abstract:
We recall the construction of the free orthomodular poset over a given orthoposet using terms.
Given an orthoposet $P$, let language $\mathcal{L}_P$ consist of an unary operation $'$, binary operation $\vee$, and a constant $c_p$ for each element $p\in P$.
Let $\mathcal{T}_P$ be the set of all terms in the language $\mathcal{L}_P$.
Given a homomorphism $f$ from $P$ into an orthomodular poset $Q$, it is possible, for some terms $\tau\in\mathcal{T}_P$, to define their values $\mathrm{val}_f(\tau)$.
This further allows to define a set of "well-formed terms" $\mathcal{W}_P \subseteq \mathcal{T}_P$ as well as operations $'$, $\vee$ on $\mathcal{W}_P$.
This definition uses a universally quantified condition in the form "for any homomorphism from $P$ into some orthomodular poset $Q$ ...".
The free orthomodular poset over the orthoposet $P$ is then defined as a quotient structure $(\mathcal{W}_P,',\vee)/{\sim}$ for some suitable congruence $\sim$.
Our aim is to simplify this definition by replacing the quantification over all homorphisms with a condition depending only on the given orthoposet. We use the observation that the membership in $\mathcal{W}_P$ as well as the results of operations $'$, $\vee$, depend only on inequalities between the elements of the orthoposet. In the language of category theory, this observation can be expressed using the existence of pushouts. |
|
| 16. 5. 2024 | Irena Jadlovská – Oscillation of linear third-order differential equations: recent results and open problems |
| Abstract: In the given talk, we first briefly mention the basic knowledge in the qualitative theory of linear third-order delay differential equations. Next, we show how to apply our novel method of iteratively improved monotonicities of nonoscillatory solutions to establish sharp upper and lower estimates for a class positive unbounded solutions. Finally, we sketch a solution of a particularly challenging open problem - lower estimation of so-called Kneser solutions - i.e., positive bounded solutions with alternating derivative signs. | |
| 30. 5. 2024 | František Silváši (Consequentia) – Interactive theorem provers |
| Abstract: We present an introduction to interactive theorem provers, arbitrarily choosing Lean. We give an overview of its metatheory and how it applies to proving theorems mechanically. We demonstrate the most important concepts by constructing the natural numbers à la Peano, which we then use to define simple operations and prove some of their properties. | |
| 26. 9. 2024 | Ján Haluška – Linearization of a sound perception |
| 10. 10. 2024 | Emília Halušková – On retract varieties of algebras |
|
Abstract:
A retract variety is defined as a class of algebras closed under isomorphisms, retracts and direct products.
D. Jakubíková-Studenovská proved in 1998 that the system of all retract varieties of monounary algebras does not form a set.
Each variety of algebras is principal (= generated by one algebra). This is not valid for retract varieties.
Dealing with set-principal (= generated by a set of algebras) retract varieties, there appear questions as
• Is each retract variety set-principal? • Is each set-principal retract variety principal? • Is a system of all set-principal retract varieties a set? The answer to all 3 questions above is no. We will demonstrate it by monounary algebras. Presented results have been obtained in joint work with Danica Jakubíková-Studenovská. |
|
| 24. 10. 2024 | Michal Hospodár – Operational Complexity in Subregular Classes (continuation) |
| Abstract: We study the state complexity of the cut operation and positive closure on classes of combinational, singleton, finitely generated left ideal, symmetric definite, star, comet, two-sided comet, ordered, star-free, and power-separating languages. We get tight upper bounds in all cases with alphabet size between 1 and 4. In most cases, the complexity in a subclass is the same as in the class of regular languages. We also present an improvement of the alphabet size in cases of intersection on finitely generated left ideals from 10 to 8 and in case of concatenation on star languages from 3 to 2. | |
| 7. 11. 2024 | Galina Jirásková – State Complexity of the Minimal Star Basis |
| Abstract: Let $L$ be a regular language not containing $\varepsilon$. We determine the state complexity of the two operations $L \to LL^+$ and $L \to L\setminus LL^+$. The latter is of interest because $L\setminus LL^+$ is the “minimal star basis”, the set of all strings of $L$ that cannot be written as the concatenation of shorter strings of $L$, a concept first studied by John Brzozowski in 1966. |