Наредни састанак Семинара биће одржан у петак, 3. октобра 2025, у сали 301ф Математичког института САНУ са почетком у 14:15.

Предавач: Stepan L. Kuznetsov, Steklov Mathematical Institute of RAS and 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 Π^0_1 up to Π^1_1, with a very interesting hyperarithmetical level in between: Σ^0_(𝜔^𝜔). 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 μMALL, the fixpoint extension of multiplicative-additive linear logic.

Напомена: Предавања можете пратити на даљину. Све информације су доступне на страници:
https://miteam.mi.sanu.ac.rs/asset/WbsehnSL4ZeTPJo6r