Petri Nets: Properties, Analysis and Applications

Petri Nets Properties Analysis And Applications-ppt Download

  • Date:22 Nov 2020
  • Views:5
  • Downloads:0
  • Size:290.00 KB

Share Presentation : Petri Nets Properties Analysis And Applications

Download and Preview : Petri Nets Properties Analysis And Applications

Report CopyRight/DMCA Form For : Petri Nets Properties Analysis And Applications


COMP290 084Graphical Representation ofAsynchronous SystemsJan 15 2004 Graphical Representation.
Petri Nets Asynchronous State Graphs Burst Mode Representation Timed Automata Petri Nets.
Reference Tadao Murata Petri nets Properties Analysisand Applications Proc of the IEEE 77 4 1989 available on class websiteLecture Notes by .
Gabriel EireaUC Berkeley Petri Nets Properties Analysis and ApplicationsGabriel Eirea.
UC BerkeleyBased on paper by T Murata Introduction History Transition enabling firing Modeling examples.
Behavioral properties Analysis methods Liveness safeness reachability Analysis synthesis of Marked Graphs Structural properties.
Modified Petri Nets Introduction Petri Nets concurrent asynchronous distributed parallel nondeterministic and or stochastic.
graphical tool visual communication aid mathematical tool state equations algebraic equations etc communication between theoreticians and.
practitioners 1962 C A Petri s dissertation U Darmstadt W Germany 1970 Project MAC Conf on Concurrent Systems andParallel Computation MIT USA 1975 Conf on Petri Nets and related Methods MIT USA .
1979 Course on General Net Theory of Processes andSystems Hamburg W Germany 1980 First European Workshop on Applications andTheory of Petri Nets Strasbourg France 1985 First International Workshop on Timed Petri Nets.
Torino Italy Applications performance evaluation communication protocols distributed software systems.
distributed database systems concurrent and parallel programs industrial control systems discrete events systems multiprocessor memory systems.
dataflow computing systems fault tolerant systems etc etc etc Definition Directed weighted bipartite graph.
places transitions arcs places to transitions or transitionsto places weights associated with each arc.
Initial marking assigns a non negative integer to each Transition firing rule A transition t is enabled if each inputplace p has at least w p t tokens.
An enabled transition may or may A firing on an enabled transition tremoves w p t from each inputplace p and adds w t p to eachoutput place p .
Firing example2H2 O2 2H2O Firing example2H2 O2 2H2O Some definitions.
source transition no inputs sink transition no outputs self loop a pair p t s t p is both an input and an output of t pure PN no self loops ordinary PN all arc weights are 1 s.
infinite capacity net places can accommodate an unlimitednumber of tokens finite capacity net each place p has a maximum capacity strict transition rule after firing each output place can thave more than K p tokens.
Theorem every pure finite capacity net can be transformedinto an equivalent infinite capacity net Modeling FSMsvend 15 candyvend 20 candy.
Modeling FSMsvend 15 candy5 state machines each transition5 5 has exactly.
one input and5 one outputvend 20 candy Modeling FSMsconflict 5 5.
or choice 5 Modeling concurrencymarked graph each place hasexactly one.
t3 incoming arc Modeling concurrencyt2 concurrency Modeling dataflowcomputation.
x a b a b copy a b xcopy a b Modeling communicationready ready.
to send to receivesend full receiveproc 1 wait proc 2receive sendreceived sent.
Modeling synchronizationwriting k reading Behavioral properties 1 Properties that depend on the initial marking Reachability.
Mn is reachable from M0 if exists a sequence offirings that transform M0 into Mn reachability is decidable but exponential Boundedness a PN is bounded if the number of tokens in each.
place doesn t exceed a finite number k for anymarking reachable from M0 a PN is safe if it is 1 bounded Behavioral properties 2 Liveness.
a PN is live if no matter what marking has beenreached it is possible to fire any transition with anappropriate firing sequence equivalent to deadlock free strong property different levels of liveness are defined.
L0 dead L1 L2 L3 and L4 live Reversibility a PN is reversible if for each marking M reachable fromM0 M0 is reachable from M relaxed condition a marking M is a home state if for.
each marking M reachable from M0 M is reachable Behavioral properties 3 Coverability a marking is coverable if exists M reachable fromM0 s t M p M p for all places p.
Persistence a PN is persistent if for any two enabled transitions the firing of one of them will not disable the other then once a transition is enabled it remainsenabled until it s fired.
all marked graphs are persistent a safe persistent PN can be transformed into amarked graph Analysis methods 1 Coverability tree.
tree representation of all possible markings root M0 nodes markings reachable from M0 arcs transition firings if net is unbounded then tree is kept finite by.
introducing the symbol Properties a PN is bounded iff doesn t appear in any node a PN is safe iff only 0 s and 1 s appear in nodes a transition is dead iff it doesn t appear in any arc.
if M is reachable form M0 then exists a node M that covers Coverability tree example Coverability tree examplet3 M1 001 dead end .
Coverability tree examplet3 M1 001 M3 1 0 dead end Coverability tree examplet3 M1 001 M3 1 0 .
dead end M4 0 1 Coverability tree examplet3 M1 001 M3 1 0 dead end .
M4 0 1 M3 1 0 t2 old Coverability tree examplet3 M1 001 M3 1 0 dead end .
M4 0 1 M6 1 0 t2 old M5 0 1 Coverability tree exampleM1 001 M3 1 0 .
001 1 0 dead end M4 0 1 M6 1 0 t2 old M5 0 1 coverability graph coverability tree.
Subclasses of Petri Nets 1 Ordinary PNs all arc weights are 1 s same modeling power as general PN moreconvenient for analysis but less efficient.
State machine each transition has exactly one input placeand exactly one output place Marked graph each place has exactly one input transition.
and exactly one output transition Subclasses of Petri Nets 2 Free choice every outgoing arc from a place is either uniqueor is a unique incoming arc to a transition.
Extended free choice if two places have some common outputtransition then they have all their outputtransitions in common Asymmetric choice or simple .
if two places have some common outputtransition then one of them has all the outputtransitions of the other and possibly more Subclasses of Petri Nets 3 AC EFC FC SM MG.
Liveness and SafenessCriteria 1 general PN if a PN is live and safe then there are nosource or sink places and source or sink.
transitions if a connected PN is live and safe then the netis strongly connected a SM is live iff the net is strongly connectedand M0 has at least one token.
a SM is safe iff M0 has at most one token Liveness and SafenessCriteria 2 a MG is equivalent to a marked directed graph arcs places nodes transitions .
a MG is live iff M0 places at least one token oneach directed circuit in the marked directed a live MG is safe iff every place belongs to adirected circuit on which M0 places exactly there exists a live and safe marking in a.
directed graph iff it is strongly connectedProc. of the IEEE, 77(4), 1989. available on class website Credits Lecture Notes by: Gabriel Eirea UC Berkeley Petri Nets: Properties, Analysis and Applications Gabriel Eirea UC Berkeley 10/8/02 Based on paper by T. Murata Outline Introduction/History Transition enabling & firing Modeling examples Behavioral properties Analysis methods Liveness ...

Related Presentations

Forming Cognitive nets amp Social nets can inspire

Page 58 This interdisciplinary research will need experts from various fields to work on it (e.g. Neuroscience, education, psychology and more) Linking theory, research and practice Relativity of various nets Living in the Paradigm of Multiple Nets Knowledge, vision, insight, cognitive-nets Visible nets, invisible nets Subject combinations ...

8 Views0 Downloads

Platform Independent Petri net Editor 2 PIPE2

Platform Independent Petri net Editor 2 (PIPE2) CS2650 Distributed Multimedia Systems Wen Xu November 23rd, 2010 About PIPE2 PIPE2 is an Java-based, open source, platform independent tool for creating and analyzing Petri nets including Generalized Stochastic Petri nets.

4 Views0 Downloads

Section 1 1 Nets and Drawings for Visualizing Geometry

An isometric drawing shows a 3-D figure using slanted lines to represent depth. Section 1.1 – Nets and Drawings for Visualizing Geometry Problem 3: What is an isometric drawing of the cube structure at the right? Section 1.1 – Nets and Drawings for Visualizing Geometry Problem 3: What is an isometric drawing of the cube structure at the right?

20 Views0 Downloads

Security and Mobility First Looking Back nets fia net

Introduction: FIA-NP Collaborating Institutions (LEAD) D. Raychaudhuri, W. Trappe, R, Martin, Y. Zhang, I. Seskar. S. Bannerjee. W. Lehr. Z. Morley Mao. B. Ramamurthy ...

13 Views0 Downloads

Keras Deep Nets for Time Series Forecasting

Time Series Forecasting. CONFIDENTIAL & PROPRIETARY. June 1, 2019. Old (mostly statistics) discipline, affected largely by ML in recent years. Time series forecasting issues (compared to other ML problems) # of available data points. How long of a history is . a good representation of . the current behavior?

27 Views0 Downloads

Generative Adversarial Nets

This raised a lot of interest in vision community. Everyone hates CNNs beating our linear classifiers, and finally on these adversarial examples our linear classifiers outperform CNNs. On CVPR 14 there were a lot of discussions. The keynote speaker gave a pretty complicated mathematical theory to patch this.

15 Views0 Downloads

Chapter 9 Neural Nets

Arial Franklin Gothic Book Wingdings 2 Calibri Perpetua Symbol Courier New Arial Black Bodoni MT Equity 1_Equity 2_Equity 3_Equity 4_Equity Microsoft Word Document Document Microsoft Office Word Document Chapter 11 – Neural Nets Basic Idea Network Structure “Feed-Forward” Model Example – Using fat & salt content to predict consumer ...

7 Views0 Downloads

Adaptive Method for Neural Nets

Title: Adaptive Method for Neural Nets Author: C K Created Date: 4/9/2006 4:53:14 PM Document presentation format: On-screen Show Other titles: Arial Times New Roman Symbol Blackadder ITC Tahoma Default Design Microsoft Photo Editor 3.0 Photo Microsoft Equation 3.0 Neural Nets: Something you can use and something to think about What are they good for Why Neural Nets General Structure of a NN ...

15 Views0 Downloads

Neural Nets Rowan University

Artificial Neural Networks 0909.560.01/0909.454.01 Spring 2002 Lecture 2 January 31, 2002 Shreekanth Mandayam Robi Polikar ECE Department Rowan University

9 Views0 Downloads

CS440 ECE448 Artificial Intelligence Lecture 25 Natural Language Processing with Neural Nets

NLP (and modern linguistics) is largely not concerned with ”prescriptive” grammar (which is what you may have learned in school), but with formal (computational) models of grammar, and with how people . actually. use language. Used by people to . communicate. Texts written by a single person: articles, books, tweets, etc. Dialogues

3 Views0 Downloads

Hydro Mechanical Properties and Stability Analysis of Four

Hydro-Mechanical Properties and Stability Analysis of Four Landslide-Prone Hillslopes in Western North Carolina. 30 October 2013. York W. Lewis1, Alexandra Wayllace1, Jonathan W. Godt2, Richard M. Wooten3,and Ning Lu1

9 Views0 Downloads

Analysis city owned properties powerpoint

404 - 406 N Ashley. No Negative Site Issues. LIHTC Eligible. High Scoring. Perfect Size to Max Out Funding. 60 - 85 units. HUD and MSHDA Funding Eligible. DDA Funding Eligible. Minimal Local Resources Needed. UM Dental Clinic Lease Expires 6/2021. Work with UM to Relocate. c

13 Views0 Downloads