The reachability problem for branching vector addition systems requires doubly-exponential space

DOI10.1016/j.ipl.2010.06.008zbMath1234.68139OpenAlexW2108820019MaRDI QIDQ407525

Ranko Lazić

Publication date: 27 March 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.06.008

zbMATH Keywords

theory of computationprogram correctness

Mathematics Subject Classification ID

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 (1)

Nonelementary Complexities for Branching VASS, MELL, and Extensions

Cites Work

• A structure to decide reachability in Petri nets
• The covering and boundedness problems for vector addition systems
• Parallel program schemata
• Two-variable logic on data trees and XML reasoning
• An Algorithm for the General Petri Net Reachability Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The reachability problem for branching vector addition systems requires doubly-exponential space