Evènement pour le groupe Séminaire Méthodes Formelles


Date 2021-05-18  07:00-07:00
TitreReachability in Vector Addition Systems is Ackermann-complete 
RésuméComplexity of the reachability problem in Vector Addition Systems (VASes) was a long standing problems for a few decades. Very recently two proofs of Ackermann-hardness were obtained independently (one by Jerome Leroux, one by us). I will present you the proof obtained in a joint work with Lukasz Orlikowski, which is based mostly on one new technique proposed in the paper: possibility of performing many zero-tests in VASes by use of just one additional counter. Recording: https://u-bordeaux-fr.zoom.us/rec/share/1CiiKX5ILxhdO_QnkVPaSo3l9lAWRlN93okSHDV7rSDkmdqOU73z8mP4SPElg3p-.dEmVj102j1GrMLiV 
LieuOnline 
OrateurWojciech Czerwinski 
Emailhttps://www.mimuw.edu.pl/~wczerwin/ 
Urlthe Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw 



Aucun document lié à cet événement.

Retour
Retour à l'index