Automata Column: The Complexity of Reachability in Vector Addition Systems

Sylvain Schmitz 1, 2
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : The program of the 30th Symposium on Logic in Computer Science held in 2015 in Kyoto included two contributions on the computational complexity of the reachability problem for vector addition systems: Blondin, Finkel, Göller, Haase, and McKenzie [2015] attacked the problem by providing the first tight complexity bounds in the case of dimension 2 systems with states, while Leroux and Schmitz [2015] proved the first complexity upper bound in the general case. The purpose of this column is to present the main ideas behind these two results, and more generally survey the current state of affairs.
Type de document :
Article dans une revue
ACM SIGLOG News, ACM, 2016, 3 (1), pp.3--21. 〈10.1145/2893582.2893585〉
Liste complète des métadonnées

Littérature citée [74 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01275972
Contributeur : Sylvain Schmitz <>
Soumis le : jeudi 18 février 2016 - 15:36:39
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : jeudi 19 mai 2016 - 10:56:51

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Sylvain Schmitz. Automata Column: The Complexity of Reachability in Vector Addition Systems. ACM SIGLOG News, ACM, 2016, 3 (1), pp.3--21. 〈10.1145/2893582.2893585〉. 〈hal-01275972〉

Partager

Métriques

Consultations de la notice

202

Téléchargements de fichiers

335