Parameterized Complexity Results for 1-safe Petri Nets

DOI10.1007/978-3-642-23217-6_24MaRDI QIDQ3090841zbMATH OpenOpenAlexFDO

Authors M. Praveen, Kamal Lodaya

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)

Abstract: We associate a graph with a 1-safe Petri net and study the parameterized complexity of various problems with parameters derived from the graph. With treewidth as the parameter, we give W[1]-hardness results for many problems about 1-safe Petri nets. As a corollary, this proves a conjecture of Downey et. al. about the hardness of some graph pebbling problems. We consider the parameter benefit depth (that is known to be helpful in getting better algorithms for general Petri nets) and again give W[1]-hardness results for various problems on 1-safe Petri nets. We also consider the stronger parameter vertex cover number. Combining the well known automata-theoretic method and a powerful fixed parameter tractability (FPT) result about Integer Linear Programming, we give a FPT algorithm for model checking Monadic Second Order (MSO) formulas on 1-safe Petri nets, with parameters vertex cover number and the size of the formula.

Recommendations

• scientific article; zbMATH DE number 1354143
• Complexity results for 1-safe nets
• Expanding the expressive power of monadic second-order logic on restricted graph classes
• On the Parameterised Intractability of Monadic Second-Order Logic
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• scientific article; zbMATH DE number 1341905
• On the parameterized intractability of monadic second-order logic
• A unified approach for deciding the existence of certain petri net paths

Cites work

• scientific article; zbMATH DE number 46872 (Why is no real title available?)
• scientific article; zbMATH DE number 1302047 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A parametric analysis of the state-explosion problem in model checking
• An application of simultaneous diophantine approximation in combinatorial optimization
• Describing parameterized complexity classes
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph Layout Problems Parameterized by Vertex Cover
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
• On the power of bounded concurrency I
• The covering and boundedness problems for vector addition systems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(5)

• Nested-unit Petri nets
• Discrete parameters in Petri nets
• Modelchecking counting properties of 1-safe nets with buffers in paraPSPACE
• A multi-parameter analysis of hard problems on deterministic finite automata
• scientific article; zbMATH DE number 1696450 (Why is no real title available?)

This page was built for publication: Parameterized Complexity Results for 1-safe Petri Nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3090841)