Performance evaluation of concurrent systems using conflict-free and persistent Petri nets

DOI10.1016/0020-0190(87)90041-XMaRDI QIDQ1108799zbMATH OpenOpenAlexFDO

Authors Jan Magott

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90041-x

zbMATH Keywords

concurrent systemscycle time problemfiring timeNP-hardnessperformance evaluationpolynomial algorithmsthree-partition problemtimed marked Petri nets

Mathematics Subject Classification ID

Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Review text

For practical reasons, the live and bounded marked Petri nets are considered in this paper. The cycle time problem (CTP) for timed marked Petri nets (TMPNs) is analyzed. For conflict-free TMPNs without self- loops, the polynomial algorithms for CTP are given. For conflict-free and persistent TMPNs, the strong NP-hardness of CTP is proved.

Recommendations

• Performance evaluation of concurrent systems using Petri nets
• New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
• Generalized M-Timed Petri Nets And Performance Evaluation Of Computer Systems
• Performance bounds for stochastic timed Petri nets
• Analytic evaluation of the cycle time on networked conflicting timed event graphs in the (Max,+) algebra

Cites work

• A decidability theorem for a class of vector-addition systems
• A new polynomial-time algorithm for linear programming
• scientific article; zbMATH DE number 3905853 (Why is no real title available?)
• scientific article; zbMATH DE number 3921988 (Why is no real title available?)
• New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
• Performance Evaluation of Asynchronous Concurrent Systems Using Petri Nets
• Performance evaluation of concurrent systems using Petri nets
• Performance evaluation of systems of cyclic sequential processes with mutual exclusion using Petri nets
• Properties of Conflict-Free and Persistent Petri Nets
• Timing Requirements for Time-Driven Systems Using Augmented Petri Nets
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(12)

• Performance analysis using Petri nets
• A valuation-based analysis of conflict-free Petri nets
• Steady-state performance evaluation of continuous mono-T-semiflow Petri nets
• New NP-Complete Problems in Performance Evaluation of Concurrent Systems Using Petri Nets
• scientific article; zbMATH DE number 4106272 (Why is no real title available?)
• Petri net extensions for modelling and validating manufacturing systems
• scientific article; zbMATH DE number 1760112 (Why is no real title available?)
• scientific article; zbMATH DE number 2104633 (Why is no real title available?)
• Analytic evaluation of the cycle time on networked conflicting timed event graphs in the (Max,+) algebra
• Performance evaluation of Petri nets centralized implementation. The execution time controller
• Performance evaluation of concurrent systems using Petri nets
• A polynomial time algorithm to decide pairwise concurrency of transitions for 1-bounded conflict-free Petri nets

This page was built for publication: Performance evaluation of concurrent systems using conflict-free and persistent Petri nets

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