The covering and boundedness problems for vector addition systems
From MaRDI portal
Publication:1242682
DOI10.1016/0304-3975(78)90036-1zbMath0368.68054OpenAlexW2055081868WikidataQ127352552 ScholiaQ127352552MaRDI QIDQ1242682
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90036-1
Related Items
Unnamed Item ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Lower bounds on the state complexity of population protocols ⋮ Coverability and Termination in Recursive Petri Nets ⋮ Waiting Nets: State Classes and Taxonomy ⋮ Enforcing opacity by insertion functions under multiple energy constraints ⋮ Robustness Against Transactional Causal Consistency. ⋮ Long-Run Average Behavior of Vector Addition Systems with States ⋮ The 4C Spectrum of Fundamental Behavioral Relations for Concurrent Systems ⋮ Partial-Observation Stochastic Games ⋮ Nonprimitive recursive complexity and undecidability for Petri net equivalences ⋮ Occam's razor applied to the Petri net coverability problem ⋮ On the complexity of resource-bounded logics ⋮ The ideal view on Rackoff's coverability technique ⋮ A counter abstraction technique for verifying properties of probabilistic swarm systems ⋮ Complexity of certain decision problems about congruential languages ⋮ Forward analysis and model checking for trace bounded WSTS ⋮ Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time ⋮ On the Coverability Problem for Pushdown Vector Addition Systems in One Dimension ⋮ The Complexity of Reversal-Bounded Model-Checking ⋮ Reducibilities Among Decision Problems for HNN Groups, Vector Addition Systems and Subsystems of Peano Arithmetic ⋮ Bounded self-stabilizing Petri nets ⋮ The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups ⋮ Unnamed Item ⋮ An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems ⋮ The complexity of reachability in distributed communicating processes ⋮ Context-free commutative grammars with integer counters and resets ⋮ Complexity of modal logics with Presburger constraints ⋮ Deciding a class of path formulas for conflict-free Petri nets ⋮ Waiting nets ⋮ On selective unboundedness of VASS ⋮ Optimal supervisory control with mean payoff objectives and under partial observation ⋮ When are emptiness and containment decidable for probabilistic automata? ⋮ Ratio and Weight Quantiles ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ On two-way weak counter machines ⋮ Linear time analysis of properties of conflict-free and general Petri nets ⋮ Verifying chemical reaction network implementations: a bisimulation approach ⋮ The reachability problem for branching vector addition systems requires doubly-exponential space ⋮ On termination and invariance for faulty channel machines ⋮ On detectability of labeled Petri nets and finite automata ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Untanglings: a novel approach to analyzing concurrent systems ⋮ The polynomial complexity of vector addition systems with states ⋮ Unnamed Item ⋮ Small vertex cover makes Petri net coverability and boundedness easier ⋮ Deciding Structural Liveness of Petri Nets ⋮ Petri nets and regular languages ⋮ Protocols with constant local storage and unreliable communication ⋮ Graph transformation for incremental natural language analysis ⋮ Quasi-static scheduling of communicating tasks ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ Aeolus: a component model for the cloud ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Extensional Petri net ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Data flow analysis of asynchronous systems using infinite abstract domains ⋮ Checking robustness between weak transactional consistency models ⋮ Directed reachability for infinite-state systems ⋮ A unified approach for deciding the existence of certain petri net paths ⋮ Verification of membrane systems with delays via Petri nets with delays ⋮ Recursive Petri nets ⋮ Verification of Immediate Observation Population Protocols ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ Forward Analysis and Model Checking for Trace Bounded WSTS ⋮ Process calculi as a tool for studying coordination, contracts and session types ⋮ ON YEN'S PATH LOGIC FOR PETRI NETS ⋮ Strategy synthesis for multi-dimensional quantitative objectives ⋮ Unnamed Item ⋮ On the decidability of fragments of the asynchronous π-calculus ⋮ Normal and sinkless Petri nets ⋮ Communicating processes, scheduling, and the complexity of nontermination ⋮ Reachability solution characterization of parametric real-time systems ⋮ Linear reachability problems and minimal solutions to linear Diophantine equation systems ⋮ Multiset rewriting for the verification of depth-bounded processes with name binding ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Concurrency, Synchronization, and Conflicts in Petri Nets ⋮ EXPSPACE lower bounds for the simulation preorder between a communication-free Petri net and a finite-state system ⋮ Parameterized verification of coverability in infinite state broadcast networks ⋮ Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads ⋮ Combining free choice and time in Petri nets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Coverability Trees for Petri Nets with Unordered Data ⋮ Unbounded-Thread Program Verification using Thread-State Equations ⋮ On minimal elements of upward-closed sets ⋮ Vector Addition System Reversible Reachability Problem ⋮ Parameterized Complexity Results for 1-safe Petri Nets ⋮ Universality Problem for Unambiguous VASS ⋮ Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States ⋮ On the Boundedness Problem for Higher-Order Pushdown Vector Addition Systems ⋮ PATH DECOMPOSITION AND SEMILINEARITY OF PETRI NETS ⋮ On the finite containment problem for Petri nets ⋮ A multiparameter analysis of the boundedness problem for vector addition systems ⋮ Boundedness, empty channel detection, and synchronization for communicating finite automata ⋮ Complexity Hierarchies beyond Elementary ⋮ Analyzing Reachability for Some Petri Nets With Fast Growing Markings ⋮ On Yen’s Path Logic for Petri Nets ⋮ Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable ⋮ Verifying Chemical Reaction Network Implementations: A Bisimulation Approach ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ Unnamed Item ⋮ Some complexity results for stateful network verification ⋮ The residue of vector sets with applications to decidability problems in Petri nets ⋮ Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. ⋮ \(K\)-diagnosability analysis of bounded and unbounded Petri nets using linear optimization ⋮ Taming past LTL and flat counter systems ⋮ Global and local views of state fairness ⋮ A taxonomy of fairness and temporal logic problems for Petri nets ⋮ A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets ⋮ Coverability, Termination, and Finiteness in Recursive Petri Nets
Cites Work
- Unnamed Item
- The equality problem for vector addition systems is undecidable
- Relationships between nondeterministic and deterministic tape complexities
- Parallel program schemata
- The Complexity of the Finite Containment Problem for Petri Nets
- Bounds on Positive Integral Solutions of Linear Diophantine Equations
