| 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.
|