On the Length of Strongly Monotone Descending Chains over ℕᵈ

Orateur : Sylvain Schmitz
12 December 2023 à 14:00

I will present the main results of this joint work with Lia Schütze, available online from arXiv, starting with Rackoff’s 1978 upper bound for the coverability problem in vector addition systems, followed by the 2013 breakthrough by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Wegrzycki on this upper bound, and finally presenting the `ideal’ viewpoint on these results and its consequences for various extensions of vector addition systems.


Salle de séminaire 4B107 (bâtiment Copernic)