Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

Details Small Vertex Cover makes Petri Net Coverability and Boundedness Easier Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

2010-09-14

arxiv.org/abs/1009.2577v1

Computer Science

Data Structures and Algorithms

Full version of the paper appearing in IPEC 2010

Scientific paper

The coverability and boundedness problems for Petri nets are known to be Expspace-complete. Given a Petri net, we associate a graph with it. With the vertex cover number k of this graph and the maximum arc weight W as parameters, we show that coverability and boundedness are in ParaPspace. This means that these problems can be solved in space O(ef(k,W)poly(n)), where ef(k,W) is some exponential function and poly(n) is some polynomial in the size of the input. We then extend the ParaPspace result to model checking a logic that can express some generalizations of coverability and boundedness.

Affiliated with

Also associated with

No associations

Rating

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Small Vertex Cover makes Petri Net Coverability and Boundedness Easier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small Vertex Cover makes Petri Net Coverability and Boundedness Easier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-395360