Parameterized Complexity Results for 1-safe Petri Nets

DOI10.1007/978-3-642-23217-6_24zbMATH Open1238.68103arXiv1106.2122OpenAlexW1556034484MaRDI QIDQ3090841FDOQ3090841

Authors: M. Praveen, Kamal Lodaya 

Publication date: 2 September 2011

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)