Coverability in 2-VASS with one unary counter is in NP

DOI10.1007/978-3-031-30829-1_10arXiv2301.13543OpenAlexW4366504015MaRDI QIDQ6091190

Filip Mazowiecki, Henry Sinclair-Banks, Karol Węgrzycki

Publication date: 24 November 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

vector addition systemscoverability problemlinear path schemes

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the reachability problem for 5-dimensional vector addition systems
• A structure to decide reachability in Petri nets
• Deterministic one-counter automata
• The covering and boundedness problems for vector addition systems
• Directed reachability for infinite-state systems
• A lower bound for the coverability problem in acyclic pushdown VAS
• An SMT-Based Approach to Coverability Analysis
• Two-variable logic on data words
• A Perfect Model for Bounded Verification
• Reachability in Succinct and Parametric One-Counter Automata
• Mixing Coverability and Reachability to Analyze VASS with One Zero-Test
• On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension
• An Algorithm for the General Petri Net Reachability Problem
• Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete
• Reachability in Two-Dimensional Unary Vector Addition Systems with States is NL-Complete
• Reachability in Petri Nets with Inhibitor Arcs
• The Reachability Problem for Two-Dimensional Vector Addition Systems with States
• The reachability problem for Petri nets is not elementary
• CONCUR 2004 - Concurrency Theory
• Computational Complexity
• Reachability in Two-Clock Timed Automata Is PSPACE-Complete