Oberseminar WS 2026/27

Das Oberseminar des Lehrstuhls für Theoretische Informatik findet dienstags 14:15-15:45 in Raum 00.131-128 (Cauerstraße 11) statt.

Das Oberseminar steht Masterstudierenden und Doktoranden sowie bei Interesse Bachelorstudierenden offen.
Die Themenwahl erfolgt nach Vereinbarung entsprechend den Schwerpunkten des Lehrstuhls. Die Vortragstermine werden am ersten Termin in der Vorlesungszeit festgelegt.

Bei Nachfragen gerne per Mail an den Seminarleiter (Prof. Dr. Lutz Schröder), Anmeldung zur Mailingliste: TCS-Seminar Mailinglist

Vorträge

Current Talks

Tuesday, 10.11.2026

Quantum Instruments as a Categorical Conditioning Procedure
Nico Wittrock (INL Braga, Portugal / HASLab, University of Minho)
Abstract
We generalise conditional probabilities to categorical quantum probability theory. This generalisation procedure is two-fold: physical (a transition from classical probability to the quantum realm) and mathematical (abstracting from calculus to category theory). It allows for a new comparison between classical and quantum information and creates a bridge to other scientific communities, such as computer science.
Our starting point is the formula P(A | B) = P(A and B) / P(B), which you might remember from high school. In the first part of this talk, we first generalise mathematically and then physically; the intermediate step consists of Markov categories as a categorical framework for classical probability. Their quantum analogue is known as semicartesian probability and only uses a symmetric monoidal structure with a terminal tensor unit; our main examples are C*-algebras, their subcategories of W*-algebras, and, in between, Pedersen–Baire envelopes. This sets the stage for a new (categorical) definition of (quantum) conditionals, based on quantum (measurement) instruments. Our main result states that conditionals exist in the categories of Pedersen–Baire envelopes, and hence in W*-algebras.
In the second part of the talk, we reverse the previous steps—first physical generalisation, then mathematical—and rediscover different notions of conditioning for quantum predicates. Our main insight is their inherent connection to quantum instruments, which have a long tradition in mathematical physics. We close with a more application-oriented discussion of quantum predicates: conjunction and an if–then–else construction open the door to quantum probabilistic programming and logic.

Upcoming Talks

Tuesday, 17.11.2026

TBA
Florian Guthmann
Abstract
TBA

Tuesday, 24.11.2026

TBA
Stefan Gebhart
Abstract
TBA

Tuesday, 01.12.2026

TBA
Tom Weißhuhn
Abstract
TBA

Tuesday, 01.12.2026

TBA
David Ugen
Abstract
TBA

Tuesday, 08.12.2026

TBA
Luciano Melodia
Abstract
TBA

Tuesday, 15.12.2026

TBA
Leon Vatthauer
Abstract
TBA

Tuesday, 15.12.2026

TBA
Hannes Schulze
Abstract
TBA

Tuesday, 12.01.2027

TBA
Jonas Forster
Abstract
TBA

Tuesday, 19.01.2027

TBA
Maximilian Rumi
Abstract
TBA

Tuesday, 19.01.2027

TBA
Tobias Forchhammer
Abstract
TBA

Tuesday, 26.01.2027

TBA
Ole Elliger
Abstract
TBA

Tuesday, 02.02.2027

TBA
Chris Römmer
Abstract
TBA

Tuesday, 02.02.2027

TBA
Carl Sörgel
Abstract
TBA

Previous Talks

Tuesday, 20.10.2026

The Duality Theory of Duality Theory
Fabian Lenke
SlidesAbstract
Categorical dualities between algebras and spaces permeate mathematics and theoretical computer science. Dualities describe the relation between algebraic and state-based models of the system under investigation, be it logic, programming language semantics or language theory. Usually, the construction of such a duality starts with a well-behaved dual adjunction between a category of algebras and a category of spaces and then investigates its structure. Here, we rather build on a recently developed idea by Nishizawa, Komorida and Katsumata: to a category of algebras, represented by a monad, we construct its canonical dual topological category of spaces with an associated dual adjunction. We also go into the other direction, constructing for every topological category a canonical monad with an associated duality. Not only do we recover many classical examples of dualities as instances, but we show that these constructions can themselves be assembled to yield a higher-order duality between all of algebra and all of topology.

Tuesday, 27.10.2026

Bialgebras for Denotational Semantics of Higher-Order Programming Languages
Stefano Volpe (SDU)
SlidesAbstract
The bialgebraic abstract GSOS framework by Turi and Plotkin provides an elegant categorical approach to modelling the operational and denotational semantics of programming and process languages. In abstract GSOS, bisimilarity is always a congruence, and it coincides with denotational equivalence. This saves the language designer from intricate, ad-hoc reasoning to establish these properties. The bialgebraic perspective on operational semantics in the style of abstract GSOS has recently been extended to higher-order languages, preserving compositionality of bisimilarity.
In the first part of the talk, I quickly recall how Turi and Plotkin use bialgebras for operational and denotational semantics of programming languages, and how their recipe has been extended to operational semantics of higher-order languages. In the second part of the talk, I present recent work [1] in which my collaborators and I develop a theory of adequate denotational semantics in higher-order abstract GSOS. In the third part of the talk, I outline two current lines of research of mine
that are aimed at improving the results above. These are:domain-theoretic denotational semantics;
denotational semantics induced by big-step operational semantics.
References: [1] Sergey Goncharov, Marco Peressotti, Stelios Tsampas, Henning Urbat and Stefano Volpe, 2026. Towards a Higher-Order Bialgebraic Denotational Semantics. Proceedings of the ACM on Programming Languages 10, ICFP (August 2026)

Tuesday, 03.11.2026

Towards a New Notion of the Parameterisation of the Burrows-Wheeler-Transform
Simon Prucker
SlidesAbstract
The Burrows-Wheeler-Transform (BWT) is a reversible transformation of text introduced by M. Burrows and D. J. Wheeler in 1994. For natural languages, the transformation rearranges a text reversibly in blocks of same symbols, enhancing the efficiency of run-length coding. On the other hand, a key application of the BWT is the identification of patterns in text. For this purpose, a parameterised version of the BWT has been introduced in order to account for pattern matching under renaming as for plagiarism checkers of source code (Ganguly et al. [SODA, 2017]).
In this talk, we will be having a look at both transformations and discuss how the notion of parameterisation for the BWT can be interpreted in a nominal setting.

Vorträge

Kalender