MISANU

ODELJENJE ZA MATEMATIKU
MATEMATIČKOG INSTITUTA SANU

Predavanja možete pratiti i online putem MITEAM stranice Odeljenja za matematiku:
https://miteam.mi.sanu.ac.rs/asset/WbsehnSL4ZeTPJo6r

PROGRAM ZA OKTOBAR 2025.

Petak, 03.10.2025. u 14:15, Kneza Mihaila 36, sala 301f i Online
Stepan L. Kuznetsov, Steklov Mathematical Institute of RAS; HSE University, Moscow, Russia
KLEENE STAR AND OTHER FIXPOINTS IN NON-COMMUTATIVE LINEAR LOGIC
Among all the algebraic operations used in informatics, the Kleene star is one of the most intriguing ones. Being, in its standard definition, an infinite union, it necessarily requires either some sort of infinitary mechanisms, or some sort of induction to be used in order to axiomatise logical systems which deal with this operation. This usually leads to algorithmic undecidability and high levels of complexity for those systems. We consider action algebras, which are algebraic structures where Kleene star is combined with residuals, i.e., division operations coordinated with the partial order. Residuals naturally correspond to some sort of non-classical implication, namely, the one from intuitionistic non-commutative linear logic. We survey old and new complexity results for logical theories of action algebras. Complexity ranges, depending on the expressive power of the theories in question, from $\Pi^0_1$ up to $\Pi^1_1$, with a very interesting hyperarithmetical level in between: $\Sigma^0_{\omega^\omega}$. In the second part of the talk, we generalize our view to other fixpoint operations which can be added to non-commutative linear logic, both in its intuitionistic and classical versions. Here our starting point is the commutative case, where the corresponding systems are various versions of $\mu$MALL, the fixpoint extension of multiplicative-additive linear logic.
Zajednički sastanak sa Odeljenjem za matematiku i Seminarom verovatnosnih logika.

Petak, 10.10.2025. u 14:15, Kneza Mihaila 36, sala 301f i Online
Stanislav O. Speranski, Steklov Mathematical Institute
ON THE COMPLEXITY OF FIRST-ORDER LOGICS OF PROBABILITY
The talk will be concerned with the result that, in terms of closure ordinals, many infinitary calculi for `first-order' logics of probability — i.e., for languages similar to those studied by M. Abadi and J. Halpern (1994) — are as hard as possible: the corresponding closure ordinals coincide with the least non-constructive ordinal. In particular, this result can be applied to various proof systems developed by Z. Ognjanović and his colleagues.
Zajednički sastanak sa Odeljenjem za matematiku i Seminarom verovatnosnih logika.

Odeljenje za matematiku je opsti matematicki seminar namenjen sirokoj publici. Predavanja su prilagodjena matematicarima i onima koji zele da to postanu.

Zoran Petrić, Odeljenje za matematiku Matematickog instituta SANU