Priced timed Petri nets

DOI10.2168/LMCS-9(4:10)2013zbMATH Open1314.68199arXiv1307.2570OpenAlexW2110309174MaRDI QIDQ2865063FDOQ2865063

Authors: Richard M. Mayr, Parosh A. Abdulla 

Publication date: 28 November 2013

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

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).

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

Recommendations

• Minimal Cost Reachability/Coverability in Priced Timed Petri Nets
• Petri nets with time and cost
• scientific article; zbMATH DE number 1794367
• A timed Petri net extended with price information
• Optimal reachability in cost time Petri nets

zbMATH Keywords

Petri netstimed automataformal verification

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (6)

• Cost-optimal timed trace synthesis for scheduling of intermittent embedded systems
• Cost Problems for Parametric Time Petri Nets*
• Title not available (Why is that?)
• A timed Petri net extended with price information
• Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata
• Parameter Synthesis for Bounded Cost Reachability in Time Petri Nets

This page was built for publication: Priced timed Petri nets

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