Skip to Main content Skip to Navigation
New interface
Journal articles

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], Inria Saclay - Ile de France
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.
Document type :
Journal articles
Complete list of metadata

Cited literature [74 references]  Display  Hide  Download
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Thursday, February 18, 2016 - 3:36:39 PM
Last modification on : Friday, July 8, 2022 - 10:04:19 AM
Long-term archiving on: : Thursday, May 19, 2016 - 10:56:51 AM


Files produced by the author(s)



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



Record views


Files downloads