Parameterized Complexity Results for 1-safe Petri Nets

DOI10.1007/978-3-642-23217-6_24zbMath1238.68103arXiv1106.2122OpenAlexW1556034484MaRDI QIDQ3090841

Kamal Lodaya, M. Praveen

Publication date: 2 September 2011

Published in: CONCUR 2011 – Concurrency Theory (Search for Journal in Brave)

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

zbMATH Keywords

parametrized complexity1-safe Petri nets

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)

Related Items

Nested-unit Petri nets ⋮ A multi-parameter analysis of hard problems on deterministic finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An application of simultaneous diophantine approximation in combinatorial optimization
• The covering and boundedness problems for vector addition systems
• Describing parameterized complexity classes
• Small vertex cover makes Petri net coverability and boundedness easier
• A parametric analysis of the state-explosion problem in model checking
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
• Integer Programming with a Fixed Number of Variables
• Graph Layout Problems Parameterized by Vertex Cover
• Minkowski's Convex Body Theorem and Integer Programming
• On the power of bounded concurrency I
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs