|
Evènement pour le groupe Séminaire Méthodes Formelles
Date | 2021-05-18 07:00-07:00 |
Titre | Reachability 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 |
Lieu | Online |
Orateur | Wojciech Czerwinski |
Email | https://www.mimuw.edu.pl/~wczerwin/ |
Url | the Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw |
Aucun document lié à cet événement. RetourRetour à l'index
| |