some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

   Volume 8 (2012)

   Volume 9 (2013)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 10 (2014)

   Volume 11 (2015)

   Volume 12 (2016)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 9, ISSUE 4, PAPER 10


Priced Timed Petri Nets

©Richard M. Mayr, University of Edinburgh
©Parosh Aziz Abdulla, Uppsala University

Abstract
We consider priced timed Petri nets, i.e., unbounded Petri nets where each token carries a real-valued clock. Transition arcs are labeled with time intervals, which specify constraints on the ages of tokens. Furthermore, our cost model assigns token storage costs per time unit to places, and firing costs to transitions. This general model strictly subsumes both priced timed automata and unbounded priced Petri nets. We study the cost of computations that reach a given control-state. In general, a computation with minimal cost may not exist, due to strict inequalities in the time constraints. However, we show that the infimum of the costs to reach a given control-state is computable in the case where all place and transition costs are non-negative. On the other hand, if negative costs are allowed, then the question whether a given control-state is reachable with zero overall cost becomes undecidable. In fact, this negative result holds even in the simpler case of discrete time (i.e., integer-valued clocks).

Publication date: November 12, 2013

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-9(4:10)2013

Hit Counts: 2964

Creative Commons