Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete

DOI10.1145/2933575.2933577zbMath1401.68096arXiv1602.00477OpenAlexW2271542264MaRDI QIDQ4635905

Ranko Lazić, Matthias Englert, Patrick Totzke

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.00477

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Coverability in 2-VASS with one unary counter is in NP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Flat Petri nets (invited talk)

This page was built for publication: Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete