רשת פטרי

רשת פטרי (Petri Net) היא אחת מתוך מספר שפות מידול מתמטיות לתיאור מערכות מבוזרות. רשת פטרי היא גרף דו-צדדי מכוון, שבו צמתים מייצגים מעברים (כלומר אירועים שעלולים להתרחש, מסומנים כפסים) ומקומות (כלומר תנאים, מסומנים כעיגולים). הקשתות המכוונות מתארות אילו מקומות הם תנאים מקדימים של אילו תנאים אוחרים (מסומנים כחצים). ישנם הטוענים כי רשתות פטרי הומצאו באוגוסט 1939 על ידי קארל אדם פטרי - בגיל 13 - על מנת לתאר תהליכים כימיים.

בדומה לסטנדרטים המקובלים בתעשייה כגון UML, BPMN ו-EPC, רשתות פטרי מציעות סימון גרפי לתהליכים הכוללים בחירה, איטרציה, וביצוע מקבילי. שלא כמו סטנדרטים אלו, לרשתות פטרי ישנה הגדרה מתמטית מדויקת של סמנטיקת הביצוע, עם תאוריה מתמטית מפותחת לניתוח תהליכים.

(א) דוגמה למסלול ברשת פטרי

יסודות רשת פטרי

רשת פטרי מורכב ממקומות, מעברים, וקשתות. קשתות מחברות בין מקום למעבר או להפך, לעולם לא בין מקומות או בין מעברים. מקומות מהם יוצאת קשת למעבר נקראים מקומות הקלט של המעבר; מקומות שאליהם נכנסות קשתות ממעבר נקראים מקומות הפלט של המעבר.

מבחינה גרפית, מקומות ברשת פטרי עשויים להכיל מספר בדיד של סימנים הנקראים אסימונים. כל חלוקה של אסימונים בין המקומות מייצגת תצורה של הרשת הנקראת סימון. באופן מופשט, מעבר של רשת פטרי עשוי לירות אם הוא מופעל, כלומר יש מספיק אסימונים בכל מקומות הקלט שלו; כאשר המעבר יורה, הוא צורך את אסימוני הקלט הנדרשים, ויוצר אסימונים במקומות הפלט שלו. ירי הוא אטומי, כלומר, צעד שאינו בר-הפרעה.

כל עוד אין מדיניות ביצוע מוגדרת, הביצוע של רשתות פטרי לא דטרמיניסטי: כאשר מספר מעברים מופעלים באותו הזמן, כל אחד מהם עשוי לירות.

מאחר והירי לא דטרמיניסטי, ואסימונים עשויים להופיע בכל מקום ברשת (אפילו באותו המקום), רשתות פטרי מתאימות לתיאור התנהגות מקבילית של מערכות מבוזרות.

הגדרה פורמלית וניסוח בסיסי

רשתות פטרי הן מערכות לתיאור מעברים בין מצבים המיישמות רשתות הנקראות רשתות אלמנטריות.

הגדרה 1. רשת היא השלשה $N=(P,T,F)$ כאשר:

1. $P$ וגם $T$ הם מספר קבוצות זרות סופי של מקומות ומעברים, בהתאמה.
2. $F\subset (P\times T)\cup (T\times P)$ הוא קבוצה של קשתות (או קשרי זרימה).

הגדרה 2. בהינתן רשת $N=(P,T,F)$, תצורה היא קבוצה C כך ש-C ⊆ P.

רשת פטרי עם מעבר מאופשר.

רשת הפטרי שמתקבלת לאחר שהמעבר יורה (רשת הפטרי התחלתית למעלה).

הגדרה 3. רשת אלמנטרית היא רשת מהצורה (EN = (N, C כאשר:

1. (N = (P, T, F היא רשת.
2. C הוא כך ש C ⊆ P הוא תצורה.

הגדרה 4. רשת פטרי היא רשת מסוג (PN = (N, M, W, המיישמת רשת אלמנטרית כך ש:

1. (N = (P, T, F היא רשת.
2. M : P → Z הוא רב-קבוצה (multiset) של מקומות, כאשר Z היא קבוצה בת מנייה. M מיישם את מושג התצורה ובדרך כלל מתואר בתרשימי רשת פטרי כסימון.
3. W : F → Z הוא רב-קבוצה של קשתות, כך שמשקל כל קשת הוא מדד של ריבוי הקשתות.

אם רשת פטרי שקולה לרשת אלמנטרית, אז Z יכול להיות קבוצה בת מנייה {0,1} ואלמנטים אלו ב-P הממופים ל-1 תחת M יוצרים תצורה. באופן דומה, אם רשת פטרי אינה רשת אלמנטרית, אז רב-הקבוצה M יכול להתפרש כמייצג קבוצה של תצורות שאינו סינגלטון. במובן זה, M מיישם מושג התצורה של רשתות אלמנטריות לרשתות פטרי.

בתרשים של רשת פטרי (ראה תרשים למעלה מימין), מקומות מתוארים בדרך כלל כעיגולים, מעברים כמלבנים צרים וארוכים וקשתות כחצים בכיוון אחד המראים קשרים של מקומות למעברים או מעברים למקומות. אם התרשים היה של רשת אלמנטרית, אז אותם מקומות בתצורה היו מסומנים כעיגולים, כאשר כל עיגול מקיף נקודה אחת הנקראת אסימון. בתרשים הנתון של רשת פטרי (ראה מימין), עיגולי המקומות יכולים להכיל אסימון אחד או יותר כדי להראות את מספר הפעמים שהמקום מופיע בתצורה. התצורה של האסימונים המפוזרים על פני תרשים רשת פטרי כל נקרא סימון.

באיור העליון (ראה מימין), המקום p₁ הוא מקום קלט של מעבר t; ואילו המקום p₂ הוא המקום מקום פלט של אותו מעבר. תהי PN₀ (איור למעלה) רשת פטרי עם סימון המוגדרת M₀ ותהי PN₁ (איור למטה) רשת פטרי עם סימון המוגדר M₁. התצורה של PN₀ מאפשרת את מעבר t בשל התכונה כי כל מקומות הקלט בעלי מספר מספיק של אסימונים (מוצגים באיורים כנקודות) ה"שווה או גדול" לריבוי הקשתות המתאימות שלהם שלהם ל-t. אם ורק אם המעבר מאופשר, המעבר יירה . בדוגמה זו, הירי של מעבר t יוצר מפה בעלת סימון המוגדרת M₁ בדמות של M₀ הנוצרת ברשת פטרי PN₁ כפי שניתן לראות באיור למטה. ניתן לתאר את חוק הירי של מעבר, כמתואר בתרשים, כחיסור מספר האסימונים ממקומות הקלט שלו השווה לריבוי קשתות הקלט בהתאמה, והוספת מספר חדש של אסימונים במקומות הפלט השווה לריבוי קשתות הפלט המתאימים.

הערה 1. המשמעות המדויקת של "שווה ל- או גדול מ-" תלוי בתכונות האלגבריות המדויקות של הוספה המיושמת על Z בחוק הירי, כאשר שינויים קלים בתכונות האלגבריות יכולים להוביל לסוגים אחרים של רשתות פטרי; לדוגמה, רשתות פטרי אלגבריות.

ההגדרה הרשמית שלהלן מבוססת באופן רופף על (פיטרסון 1981). ישנן הגדרות חלופיות רבות.

סמנטיקה

גרף רשת פטרי (מכונה לעתים רשת פטרי, ראו למטה) הוא 3-יה $(S,T,W)\!$ , כאשר:

• S היא קבוצה סגורה של מקומות

• T היא קבוצה סגורה של מעברים

• S ו-T הן קבוצות זרות, כלומר פריט לא יכול להיות גם מקום וגם מעבר.

• $W:(S\times T)\cup (T\times S)\to \mathbb {N}$ היא קבוצה בת-חזרות של קשתות, כלומר היא מקצה לכל קשת מספר שלם אי-שלילי, ריבוי הקשת (או משקל); שים לב כי קשת לא יכולה לקשר שני מקומות או שני מעברים.

רלציית הזרימות היא קבוצת הקשתות: $F=\{(x,y)\mid W(x,y)>0\}$. בספרי לימוד רבים, קשתות יכולות להיות בעלות ריבוי 1. ספרים אלו בדרך כלל מגדירים רשתות פטרי על ידי F במקום W. כשמשתמשים במוסכמה הזו, גרף רשת פטרי הוא מולטיגרף מכוון $(S\cup T,F)$ עם מחיצות הצמתים S ו-T.

קבוצת הקלט של מעבר t הוא קבוצת מקומות הקלט שלו: ${}^{\bullet }t=\{s\in S\mid W(s,t)>0\}$; קבוצת הפלט שלו הוא קבוצת המקומות $t^{\bullet }=\{s\in S\mid W(t,s)>0\}$. ההגדרות של קבוצות הקלט והפלט של מקומות הן מקבילות.

סימון של רשת פטרי (גרף) הוא רב-קבוצה של המקומות שלה, למשל המיפוי $M:S\to \mathbb {N}$. אנו אומרים כי הסימון מקצה לכל מקום מספר של אסימונים.

רשת פטרי (יש המכנים אותה רשת פטרי מסומנת, ראה למעלה) היא 4-יה $(S,T,W,M_{0})\!$, כאשר

• $(S,T,W)$ הוא גרף רשת פטרי;
• $M_{0}$ הוא הסימון ההתחלתי, סימון של גרף רשת פטרי.

סמנטיקת ביצוע

מילולית:

• ירי מעבר t בסימון Mצורך $W(s,t)$ אסימונים מכל אחד ממקומות הקלט שלו s, ומייצר $W(t,s)$ אסימונים בכל אחד ממקומות הפלט שלו s
• מעבר מאופשר (הוא מסוגל לירות) ב-M אם ישנם מספיק אסימונים במקומות הקלט שלו על מנת שהצריכה תהיה אפשרית, כלומר אם ורק אם $\forall s:M(s)\geq W(s,t)$.

אנו בדרך כלל מתעניינים במה שעשוי לקרות כאשר מעברים עלולים לירות ברציפות באופן שרירותי.

אנו אומרים כי סימון $M'$ הוא נגיש מסימון M בצעד אחד אם $M\to _{G}M'$; אנו אומרים כי הוא נגיש מ-M אם $M{\to _{G}}^{*}M'$ כאשר: ${\to _{G}}^{*}$ הוא הסגור הטרנזיטיבי של $\to _{G}$; כלומר, אם הוא נגיש ב-0 צעדים או יותר.

עבור רשת פטרי (מסומנת) $N=(S,T,W,M_{0})\!$, אנו מתעניינים ביריות שעשויות להתרחש החל מהסימון ההתחלתי $M_{0}$. קבוצת הסימונים הנגישים שלו היא הקבוצה $R(N)\ {\stackrel {D}{=}}\ \{M'\mid M_{0}{\to _{(S,T,W)}}^{*}M'\}$.

גרף הנגישות של N הוא רלציית המעברים $\to _{G}$ המוגבל על ידי הסימונים הנגישים שלו $R(N)$. זהו מרחב המצבים של הרשת.

רצף היריות של רשת פטרי עם כרף G וסימון התחלתי $M_{0}$ הוא רצף של מעברים ${\vec {\sigma }}=\langle t_{i_{1}}\ldots t_{i_{n}}\rangle$ כך ש-$M_{0}\to _{G,t_{i_{1}}}M_{1}\wedge \ldots \wedge M_{n-1}\to _{G,t_{i_{n}}}M_{n}$. קבוצת רצפי הירי מסומנת $L(N)$.

וריאציות של ההגדרה

כפי שצוין לעיל, וריאציה נפוצה היא לאסור ריבוי קשתות והחלפת רב-הקבוצה של קשתות W בקבוצה פשוטה, המכונה קשר הזרימה, $F\subseteq (S\times T)\cup (T\times S)$. זה לא מגביל את כוח ההבעה היות ושתיהן מסוגלות לייצג זו את זו. וריאציה נפוצה נוספת, למשל, ב-Desel and Juhás (2001), הוא לאפשר סימון קיבולות של מקומות. נושא זה נדון תחת הרחבות בהמשך.

ניסוח במונחים של וקטורים ומטריצות

הסימונים של רשת פטרי $(S,T,W,M_{0})\!$ יכולים להיחשב כוקטורים של מספרים שלמים אי-שליליים באורך $|S|$.

רלציית המעבר שלה יכולה להיות מתוארת כזוג של $|S|$ על ידי המטריצות $|T|$:

• $W^{-}$ המוגדר $\forall s,t:W^{-}[s,t]=W(s,t)$.

• $W^{+}$ המוגדר $\forall s,t:W^{+}[s,t]=W(t,s)$.

ואז ההפרש ביניהן

• $W^{T}=W^{+}-W^{-}$ יכול לשמש לתיאור הסימונים הנגישים במונחים של כפל מטריצות, כדלהלן.

עבור כל רצף של מעברים w, כתוב $o(w)$ עבור הוקטור הממפה כל מעבר למספר המופעים שלו ב-w. ואז יש לנו

• $R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\!$ הוא רצף יריות של $N\}\!$.

שים לב שחובה כי W הוא רצף ירי; אפשור רצפים אקראיים של מעברים בדרך כלל מייצר קבוצה גדולה יותר.

(ב) דוגמה לרשת פטרי

$W^{+}={\begin{bmatrix}*&t1&t2\\p1&0&1\\p2&1&0\\p3&1&0\\p4&0&1\end{bmatrix}}$

$W^{-}={\begin{bmatrix}*&t1&t2\\p1&1&0\\p2&0&1\\p3&0&1\\p4&0&0\end{bmatrix}}$

$W^{T}={\begin{bmatrix}*&t1&t2\\p1&-1&1\\p2&1&-1\\p3&1&-1\\p4&0&1\end{bmatrix}}$

$M_{0}={\begin{bmatrix}1&0&2&1\end{bmatrix}}$

תכונות מתמטיות של רשתות פטרי

אחד הגורמים לכך שרשתות פטרי הן מעניינות הוא שהן מספקות איזון בין כוח המידול ויכולת ניתוח: ניתן לקבוע באופן אוטומטי דברים רבים על מערכות מקביליות ברשתות פטרי, למרות שחלק מהדברים הללו יקרים מאוד לקביעה במקרה הכללי. מספר תת-קבוצות של רשתות פטרי שכבר נלמדו עדיין מסוגלות למדל קבוצות מעניינות של מערכות במקביליות, בעוד הבעיות אלה הופכות קלות יותר.

ניתן למצוא סקירה על בעיות החלטה כאלו, עם תוצאות כריעות וסיבוכיות של רשתות פטרי ושל מספר תתי-קבוצות, ניתן למצוא בEsparza and Nielsen (1995). Esparza ונילסן (1995)

נגישות

בעיית הנגישות (reachability) של רשתות פטרי היא ההחלטה, בהינתן רשת הפטרי N והסימון M, האם $M\in R(N)$.

ברור כי זהו עניין של ההליכה בגרף הנגישות המוגדר לעיל, עד שנגיע לציון המבוקש או עד שנדע כי כבר לא ניתן להגיע אליו. זה יותר קשה ממה שזה נראה בהתחלה: גרף הנגישות הוא בדרך כלל אינסופי, וזה לא קל לקבוע מתי זה בטוח להפסיק.

למעשה, בעיה זו הוצגה כבעיה בעלת קושי EXSPACE שנים לפני שהיא הוצגה בכלל כבת-הכרעה (Mayr, 1981). עדיין מתפרסמים מחקרים על איך לבצע זאת ביעילות.

אמנם נדמה כי נגישות היא כלי טוב למציאת מצבים שגויים, אך בדרך כלל הגרף מכיל יותר מדי מצבים מכדי לחשב. על מנת להקל על בעיה זו, משתמשים בדרך כלל בלוגיקה עיתית לינארית (Linear Temporal Logic) בשילוב עם שיטת התמונה האנליטית בכדי להוכיח שלא ניתן להגיע למצבים כאלו. LTL משתמש בטכניקת ההחלטה למחיצה בכדי למצוא האם אכן ניתן להגיע למצב, על ידי מציאת קבוצת תנאים הכרחיים על מנת להגיע אליו, ואז מוכיח כי תנאים אלו אינם מספקים.

חיות

רשת פטרי שבה $t_{0}$ הוא מת, בעוד עבור כל $j>0,$ $t_{j}$ הוא בעל חיות $L_{j}$

ניתן לתאר רשת פטרי כבעלת דרגות חיות שונות $L_{1}-L_{4}$. רשת פטרי $(N,M_{0})$ נקראת בעלת חיות $L_{k}$ אם ורק אם כל המעברים שלה הם בעלי חיות $L_{k}$, כאשר מעבר הוא

• מת, אם הוא לעולם לא יוכל לירות, כלומר הוא לא באף רצף ירי ב-$L(N,M_{0})$.
• בעל חיות $L_{1}$ (בעל סיכוי לירות), אם ורק אם הוא עשוי לירות, כלומר הוא ברצף ירי ב-$L(N,M_{0})$.
• בעל חיות $L_{2}$ אם ורק אם הוא מסוגל לראות באופן שרירותי, כלומר אם עבור כל מספר שלם וחיובי k, הוא קורה לפחות k פעמים ברצף ירי כלשהו ב-$L(N,M_{0})$
• בעל חיות $L_{3}$ אם ורק אם הוא יכול לירות אינסוף פעמים, כלומר עבור כל מספר שלם וחיובי k, הוא קורה לפחות k פעמים בV, עבור מספר קבוצות סגורות-קידומת של של רצפי ירי ${}_{V\subseteq L(N,M_{0})}$.
• בעל חיות $L_{4}$ (חי) אם ורק אם הוא תמיד יירה, כלומר הוא בעל חיות $L_{1}$ בכל סימון נגיש ב-$R(N,M_{0})$.

שימו לב כי הדרשות מחמירות בסדר עולה: חיות $L_{j+1}$ מרמזת חיות $L_{j}$ עבור ${}_{j\in {1,2,3}}$.

הגדרות אלו הן בהתאם לסקירה של Murata, אשר משתמש בחיות $L_{0}$ כמונח עבור מת.

חסימות

גרף הנגישות של N2.

מקום ברשת פטרי נקרא חסום-k אם הוא לא מכיל יותר מ-k אסימונים בכל הסימונים הנגישים, כולל הסימון ההתחלתי; הוא נחשב כבטוח אם הוא חסום-1; הוא קבוצה חסומה k אם הוא חסום-k עבור k כלשהו.

רשת פטרי (מסומנת) נקראת חסומה-k, בטוחה או חסומה כאשר כל המקומות בה מוגדרים כך. רשת פטרי (גרף) נקראת חסומה מבנית אם היא חסומה עבור כל סימון התחלתי אפשרי.

שים לב כי רשת היא חסומה אם ורק אם גרף הנגישות שלה הוא אינסופי.

ניתן לקבוע חסימות על ידי בחינת בעיות כיסוי, על ידי בניית עץ קארפ-מילר.

כפיית חסימות באופן מפורש על מקומות ברשת נתונה עשויה להיות שימושית. זה יכול לשמש מידול של משאבים מוגבלים.

הגדרות מסוימות של רשתות פטרי מתירות זאת באופן מפורש כתכונה תחבירית. באופן רשמי, רשתות פטרי עם קיבולת מקומות יכולות להיות מוגדרות כ-nיות $(S,T,W,C,M_{0})$, כאשר $(S,T,W,M_{0})$ היא רשת פטרי, $C:P\rightarrow \!\!\!\shortmid I\!N$ הקצאה של קיבולות לחלק או כל המקומות, ורלציית המעברים היא זה שבדרך כלל מוגבל לסימונים כאשר כל מקום עם קיבולת יש לכל היות מספר אסימונים כזה.

רשת פטרי לא חסומה, N.

למשל אם ברשת N, מוקצה הקיבולת 2 לשני מקומות, נקבל רשת פטרי עם קיבולות מקום, נניח N2; גרף הנגישות שלה מוצג בצד ימין.

רשת פטרי חסומה-2, המתקבלת על ידי הרחבת N ב"מקומות-נגד".

לחלופין, ניתן לחסום מקומות על ידי הרחבת הרשת. ליתר דיוק, מקום יכול להיות חסום-k על ידי הוספת "מקום-נגד" עם זרימה הפוכה אליו, והוספת אסימונים כך שסך האסימונים במקומות-הנגד יהיה k.

רשתות פטרי בדידות, רציפות והיברידיות

כמו גם לאירועים בדידים, יש רשתות פטרי לתהליכים רציפים ובדידים-רציפים היברידיים, שהם שימושיים בתורת הבקרה בדידה, רציפה ושליטה, וקשורה לתורת האוטומטים בדידים, רציפים והיברידיים.

הרחבות

ישנן הרחבות רבות לרשתות פטרי. חלקן בעלות תאימות מלאה לאחור (למשל רשתות פטרי צבעוניות) עם רשת רשת הפטרי המקורית. ישנם המוסיפים תכונות שלא ניתנות למידול בפורמליזם של רשת הפטרי המקורית (למשל רשתות פטרי מתוזמנות). למרות שמודלים בעלי תאימות לאחור אינם מיישמים את כוח החישוב של רשתות פטרי, ייתכן שיש להם ייצוגים תמציתיים והם עשויים להיות יותר נוחים למידול. לעתים הרחבות שלא ניתן לייצג כרשת פטרי מקורית הן מאוד חזקות, אך בדרך כלל חסרות את המגוון הרחב של כלים מתמטיים הזמינים לניתוח ברשתות פטרי רגילות.

המונח רשתות פטרי ברמת-על משמש פורמליזם של רשתות פטרי המיישמות את הפורמליזם של אשת פטרי מקורית; זה כולל רשתות פטרי צבעוניות, רשתות פטרי היררכיות כגון רשתות בתוך רשתות, וכל שאר ההרחבות הנידונות בפרק זה. המונח גם משמש במיוחד את רשתות הפטרי הצבעוניות הנתמכות על ידי כלי CPN.

רשימה קצרה של הרחבות אפשריות:

• סוגים נוספים של קשתות; שני סוגים נפוצים הם:
  • קשת איפוס אינה אינה מהווה תנאי מקדים של ירי, ומרוקנת את המקום כשהמעבר יורה; זה גורם לחוסר יכולת לקבוע את הנגישות, בעוד שתכונות אחרות, כגון סיום, ניתנות להכרעה;
  • קשת בולמת גורמת לכך שמעבר יכול לירות רק אם המקום של התנאי המקדים ריק; זה מאפשר לבטא חישובים שרירותיים על מספר אסימונים, מה שהופך את הפורמליזם לשלם-טיורינג) ומרמז את קיומה של רשת אוניברסלית.

• ברשתות פטרי סטנדרטיות, לא קיימת אבחנה בין סוגים שונים של אסימונים. ברשת פטרי צבעונית, לכל אסימון יש ערך. בכלים פופולריים לרשתות פטרי צבעוניות כגון CPN, הערכים של האסימונים מוקלדים, וניתן לבדוק אותם (באמצעות guard expressions) ולבצע עליהם מניפולציות באמצעות שפת תכנות פונקציונלית. תת-סוג של רשתות פטרי צבעוניות הוא רשתות פטרי בנויות היטב, בהן הקשת וביטוי ה-guard, מוגבלים להקל על ניתוח הרשת.

• הרחבה נוספת של רשתות פטרי היא היררכיה. רשת זו בצורה שונות של מבט תומכת ברמות שונות של מורכבות והפשטה נחקרה על ידי Fehling. צורה שונה של היררכיה נמצאת במה שמכונה רשתות פטרי עצמים או מערכות עצמים, בהן רשת פטרי יכולה להכיל רשתות פטרי כאסימונים לרבות היררכיה של רשתות פטרי מקוננות שמתקשרות על ידי סנכרון מעברים ברמות שונות. ראה להצגה בלתי-פורמלית של רשתות פטרי עצמים.

• מערכת הוספת וקטורים עם מצבים (VASS) היא פורמליזם שקול לרשתות פטרי. עם זאת, באופן שטחי ניתן לראות בה כהכללה של רשתות פטרי. חשוב על אוטומט סופי כאשר כל מעבר מסומן על ידי מעבר מרשת פטרי. רשת הפטרי אם כן מסונכרנת עם האוטומט הסופי, כלומר מעבר באוטומט מתבצע באותו זמן עם המעבר המקביל ברשת הפטרי. ניתן לבצע מעבר באוטומט רק אם המעבר המקביל ברשת הפטרי מאופשר, ומעבר יכול לירות ברשת הפטרי אם קיים מעבר מהמצב הנוכחי באוטומט המסומן לפיו. (ההגדרה של VASS בדרך כלל מנוסחת באופן מעט שונה.)

• רשתות פטרי מתעדפות מוסיפות תכונות למעברים, לפיהן מעבר אינו יכול לירות אם מעבר בעל עדיפות גבוהה יותר מאופשר (כלומר הוא יכול לירות). לפיכך, מעברים נמצאים בקבוצות עדיפויות, ולמשל מעברים בקבוצת עדיפות 3 מסוגלים לירות אם כל המעברים בקבוצות 1 ו-2 כבויים. בתוך קבוצת עדיפות, הירי עודנו לא דטרמיניסטי.

• תכונת אי-הדטרמיניסטיות הייתה יקרת-ערך, משום שהיא מאפשרת למשתמש לפשט מספר רב של תכונות (בהתאם לתכלתית הרשת). במקרים מסוימים, לעומת זאת, הצורך נוצר בכדי למדל תזמון, ולא רק את מבנה המודל. למילוי צרכים אלו, התפתחו רשתות פטרי מתוזמנות, בהן ישנם מעברים המתוזמנים, וייתכנו גם מעברים שאינם מתוזמנים (במידה ויש, מעברים שאינם מתוזמנים בעלי עדיפות כבוהה יותר מאלו שכן). תת-קבוצה של רשתות פטרי מתוזמנות היא רשתות פטרי סטוכסטיות המוסיפות זמן לא דטרמיניסטי על ידי

אקראיות המעברים הניתן להתאמה. ההתפלגות המעריכית בדרך כלל משמשת 'לתזמן' את הרשתות הללו. במקרה זה, גרף הנגישות של הרשת יכול לשמש כשרשרת מרקוב.

• רשת פטרי דואליסטית (dP-Nets) היא הרחבה של רשת פטרי שפותחה על ידי E. Dawis, et al. על מנת לייצג באופן טוב יותר תהליך בעולם האמיתי. רשתות פטרי דואליסטיות מאזנות את הדואליות של שינוי/חוסר שינוי, אקטיביות/פסיביות, (טרנספורמציה) זמן/מקום, וכו', ומבחינות בין רשתות פטרי המייצגות טרנספורמציה של זמן לכאלו המייצגות טרנספורמציה של מקום. רעיון זה מעניק לרשת פטרי דואליסטית את המאפיין הייחודי שהוא סימון טרנספורמציה, כלומר כשהטרנספורמציה "פועלת" היא מסומנת. זה מאפשר לטרנספורמציה לירות (או להיות מסומנת) מספר פעמים וכך מתאפשר ייצוג של התנהגות תפוקה של תהליך. סימון הטרנספורמציה מניח כי זמן טרנספורמציה מוכרח להיות גדול מאפס. זמן טרנספורמציה באורך אפס המשמש רשתות פטרי רבות, אמנם קורץ מבחינה מתמטית, אך אינו שימושי בייצוג של תהליכים בעולם האמיתי. רשתות פטרי דואליסטיות גם מנצלות את האבסטרקציה של רשתות פטרי היררכיות, על מנת לתאר ארכיטקטורת תהליך. מערכות תהליכים מורכבות ממודלות כסדרה של רשתות פטרי פשוטות יותר המקושרות ביניהן באמצעות רמות שונות של הפשטה. ארכיטקטורת התהליך של מתג מודגמת ב, שבו דרישות פיתוח מאורגנות סביב מבנה המערכת המתוכננת. רשתות פטרי דואליות מאפשרות למדל, לחקור ולשפר כל תהליך בעולם האמיתי, כגון מערכות מחשוב, תהליכים עסקיים, תעבורה, זרימה, וכו'.

ישנן עוד הרחבות רבות לרשתות פטרי, עם זאת, חשוב לזכור כי ככל שמורכבות הרשת עולה במונחים של תכונות מורחבות, קשה יותר להשתמש בכלים סטנדרטים על מנת להעריך תכונות מסוימות של הרשת. בשל כך, זה רעיון טוב להשתמש בסוג הרשת הכי פשוט שאפשר עבור משימת מידול.

הגבלות

המחשה גרפית של סוגי רשתות פטרי

במקום להרחיב את הפורמליזם של רשת פטרי, אנו יכולים גם להתבונן על הגבלתו, ולהתבונן בסוגים מסוימים של רשתות פטרי, שהושגו על ידי הגבלת התחביר באופן מסוים. רשתות פטרי רגילות הן הרשתות בהן כל משקולות הקשתות הן 1. בדרך כלל נעשה שימוש ומחקר של הגבלות נוספות של רשתות פטרי רגילות:

1. באוטומט סופי (SM), כל מעבר יש קשת נכנסת אחת

וקשת יוצאת אחת, וכל הסימונים בעלי אסימון אחד בדיוק. כתוצאה מכך, לא יכולה להיות מקביליות, אך יכול להיוותר קונפליקט (כלומר אי-דטרמיניזם). מתמטית: $\forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1$

1. בגרף מכוון (MG), לכל מקום יש קשת נכנסת אחת וקשת יוצאת אחת. דהינו, שלא יכול להיווצר קונפליקט, אך יכולה להיות מקביליות. מתמטית: $\forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1$
2. ברשת בחירה חופשית (FC), - כל קשת ממקום למעבר היא הקשת היחידה ממקום זה או הקשת היחידה למעבר זה. כלומר יכולים להתקיים הן מקביליות והן קונפליקט, אך לא באותו הזמן. מתמטית: $\forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})$
3. בחירה חופשית מורחבת (EFC) - רשת פטרי שיכולה להפוך ל-FC.
4. ברשת בחירה אסימטרית (AC), מקביליות וקונפליקט (בסיכום, בלבול) יכולים לקרות, אך לא באופן סימטרי. מתמטית: $\forall s_{1},s_{2}\in S:(s_{1}{}^{\bullet }\cap s_{2}{}^{\bullet }\neq \emptyset )\to [(s_{1}{}^{\bullet }\subseteq s_{2}{}^{\bullet })\vee (s_{2}{}^{\bullet }\subseteq s_{1}{}^{\bullet })]$

רשתות זרימה (רשתות WF)

רשתות זרימה הן תת-קבוצה של רשתות פטרי שמטרתן למדל את זרימת פעילויות התהליך. מעברי רשת זרימה מוקצות עבור משימות או פעילויות, ומקומות מוקצים לתנאי קדם או תנאים אוחרים. לרשתות הזרימה ישנן דרישות מבניות ופעולה נוספות, בעיקר התוספת של של מקום קלט יחיד (מקור) ללא מעברים קודמים, ומקום פלט (בור) ללא מעברים עוקבים. בהתאם לכך, ניתן להגדיר סימוני התחלה וסוף המייצגים את סטטוס התהליך.

רשתות זרימה הן בעלות תכונת הנאותות, המציינת כי תהליך עם סימון התחלתי של k אסימונים במקור, מסוגל להגיע לסימון הסופי שלו עם k אסימונים בבור (מוגדר כרשת זרימה נאותה-K). בנוסף, כל המעברים בתהליך יכולים לירות (כלומר עבור כל מעבר ישנו מצב נגיש בו המעבר מאופשר). רשת זרימה נאותה-גנרית (נאותה-G) מוגדרת נאותה-K עבור כל k>0.

מסלול מכוון ברשת פטרי מוגדר כרצף צמתים (מקומות ומעברים) המקושרים באמצעות קשתות מכוונות. מסלול אלמנטרי מכיל כל צומת ברצף פעם אחת בלבד.

רשת פטרי מתוחזקת היטב היא רשת שבה אין מסלולים אלמנטריים שונים לגמרי בין מקום ומעבר (או מעבר ומקום), כלומר אם ישנם שני מסלולים בין זוג הצמתים, אזי המסלולים הללו חולקים צומת. רשת זרימה מתוחזקת-היטב מעגלית היא נאותה (נאותה-G).

רשת זרימה מורחבת היא רשת פטרי המורכבת מרשת זרימה עם מעבר נוסף t (מעבר משוב). מקום הבור מקושר כמקום הקלט של מעבר t והמקור כמקום הפלט שלו. ירי של מעבר זה גורם לאיטרציה של התהליך (שים לב: רשת הזרימה המורחבת היא לא רשת זרימה).

רשת זרימה WRI (מתוחזקת היטב עם איטרציה רגילה) היא רשת זרימה אי-מעגלית מורחבת. רשת WRI-WF יכולה להיבנות כצירוף של רשתות, כלומר החלפת מעבר ברשת WRI-WF בתת-רשת מסוג WRI-WF. התוצאה היא גם רשת WRI-WF. רשתות WRI-WF הן גם נאותות-G, לכן על ידי שימוש באבני בניין מסוג רשת WRI-WF בלבד, ניתן להשיג רשתות זרימה שהן נאותות-G לפי המבנה.

מטריצת מבנה העיצוב (DSM) יכולה למדל יחסי תהליך, ולשמש לתכנון תהליכים. רשתות DSM הן מימושן של תכניות מבוססות DSM לתהליכי זרימה על ידי רשתות פטרי, ושקולות לרשתות WRI-WF. תהליך בניית רשת ה-DSM מבטיח את תכונת הנאותות של הרשת המתקבלת.

מודלים אחרים של מקביליות

הוצעו דרכים אחרות למידול חישוב במקבילי, כולל אלגברת תהליך, מודל השחקן ותיאורית העקבות. דגמים שונים מספקים פשרות של מושגים כמו קומפוזיציונליות, מודולריות, ולוקליות.

גישה לקישור חלק מהמודלים לעיל מוצע בפרק על ידי ווינסקל ונילסן.

תחומי יישום

• Business Process Management
• ניתוח מידע
• סימולציה
• עיצוב תוכנה

ראו גם

• אוטומט סופי

לקריאה נוספת

• Cardoso, Janette; Camargo, Heloisa (1999). Fuzziness in Petri Nets. Physica-Verlag. ISBN 3-7908-1158-0.
• Grobelna, Iwona (2011). "Formal verification of embedded logic controller specification with computer deduction in temporal logic". Przeglad Elektrotechniczny. 87 (12a): 47–50.
• Jensen, Kurt (1997). Coloured Petri Nets. Springer Verlag. ISBN 3-540-62867-3.
• Котов, Вадим (1984). Сети Петри (Petri Nets, in Russian). Наука, Москва.
• Pataricza, András (2004). Formális módszerek az informatikában (Formal methods in informatics). TYPOTEX Kiadó. ISBN 963-9548-08-1.
• Peterson, James L. (1977). "Petri Nets". ACM Computing Surveys. 9 (3): 223–252. doi:10.1145/356698.356702. {{cite journal}}: לא תקין |ref=harv (עזרה)
• Peterson, James Lyle (1981). "Petri Net Theory and the Modeling of Systems". Prentice Hall. ISBN 0-13-661983-5. {{cite journal}}: Cite journal requires |journal= (עזרה); לא תקין |ref=harv (עזרה)
• Petri, Carl A. (1962). Kommunikation mit Automaten (Ph. D. thesis). University of Bonn.
• Petri, Carl Adam; Reisig, Wolfgang. "Petri net". Scholarpedia. 3 (4): 6477. doi:10.4249/scholarpedia.6477. נבדק ב-2008-07-13.
• Reisig, Wolfgang (1992). A Primer in Petri Net Design. Springer-Verlag. ISBN 3-540-52044-9.
• Riemann, Robert-Christoph (1999). Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus. Herbert Utz Verlag. ISBN 3-89675-629-X.
• Störrle, Harald (2000). Models of Software Architecture - Design and Analysis with UML and Petri-Nets (PDF). Books on Demand. ISBN 3-8311-1330-0.
• Zhou, Mengchu; Dicesare, Frank (1993). Petri Net Synthesis for Discrete Event Control of Manufacturing Systems. Kluwer Academic Publishers. ISBN 0-7923-9289-2.
• Zhou, Mengchu; Venkatesh, Kurapati (1998). Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach. World Scientific Publishing. ISBN 981-02-3029-X.
• Zaitsev, Dmitry (2013). Clans of Petri Nets: Verification of protocols and performance evaluation of networks. LAP LAMBERT Academic Publishing. ISBN 978-3-659-42228-7.