Small vertex cover makes Petri net coverability and boundedness easier

DOI10.1007/s00453-012-9687-6zbMath1410.68258arXiv1009.2577OpenAlexW2754374124MaRDI QIDQ1949744

M. Praveen

Publication date: 16 May 2013

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

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

zbMATH Keywords

Petri netsvertex coverparameterized complexity\textsc{ParaPspace}

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Specification and verification (program logics, model checking, etc.) (68Q60) 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 (2)

On selective unboundedness of VASS ⋮ Parameterized Complexity Results for 1-safe Petri Nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On selective unboundedness of VASS
• A unified approach for deciding the existence of certain petri net paths
• The covering and boundedness problems for vector addition systems
• All structured programs have small tree width and good register allocation
• Lectures on Petri nets. 1: Basic models. Advances in Petri nets
• A multiparameter analysis of the boundedness problem for vector addition systems
• Modeling multithreaded applications using Petri nets
• Describing parameterized complexity classes
• Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
• ON YEN'S PATH LOGIC FOR PETRI NETS
• Reachability in Succinct and Parametric One-Counter Automata
• Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads
• Model Checking Succinct and Parametric One-Counter Automata
• Graph Layout Problems Parameterized by Vertex Cover
• Context-Bounded Analysis for Concurrent Programs with Dynamic Creation of Threads
• On Yen’s Path Logic for Petri Nets
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Term Rewriting and Applications

This page was built for publication: Small vertex cover makes Petri net coverability and boundedness easier