רשת פטרי

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

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

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

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

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

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

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

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

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

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

הגדרה 1. רשת היא גרף דו-צדדי. מקובל לתאר את הרשת כשלשה סדורה ${\displaystyle N=(P,T,F)}$ כאשר:

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

הגדרה 2. בהינתן רשת ${\displaystyle N=(P,T,F)}$, כל תת-קבוצה C של P נקראת תצורה (configuration).

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

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

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

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

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

1. (N = (P, T, F היא רשת.
2. M : P → Z היא מולטי קבוצה של מקומות, כאשר 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 בחוק ההפעלה, כאשר שינויים קלים בתכונות האלגבריות יכולים להוביל לסוגים אחרים של רשתות פטרי; לדוגמה, רשתות פטרי אלגבריות^[3].

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

תחביר

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

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

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

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

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

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

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

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

מילולית:

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

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

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

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

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

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

הגדרות חלופיות

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

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

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

רלציית המעברים שלה יכולה להיות מתוארת כזוג מטריצות ${\displaystyle |S|}$ על ${\displaystyle |T|}$:

• ${\displaystyle W^{-}}$ המוגדרת ${\displaystyle \forall s,t:W^{-}[s,t]=W(s,t)}$ (מטריצת הקשתות מקום-מעבר).
• ${\displaystyle W^{+}}$ המוגדרת ${\displaystyle \forall s,t:W^{+}[s,t]=W(t,s)}$ (מטריצת הקשתות מעבר-מקום).

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

• ${\displaystyle W^{T}=W^{+}-W^{-}}$ יכול לשמש לתיאור הסימונים הנגישים במונחים של כפל מטריצות, כדלהלן. עבור כל רצף מעברים w, כתוב ${\displaystyle o(w)}$ עבור הווקטור הממפה כל מעבר למספר המופעים שלו ב-w. ואז נקבל
• ${\displaystyle R(N)=\{M\mid \exists w:M=M_{0}+W^{T}\cdot o(w)\wedge w\!}$ הוא רצף הפעלות של ${\displaystyle N\}\!}$.

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

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

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

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

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

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

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

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

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

נגישות

בעיית הנגישות (reachability) של רשתות פטרי היא להכריע, בהינתן רשת הפטרי N והסימון M, האם ${\displaystyle M\in R(N)}$, האם ניתן להגיע לסימון M על ידי רצף כלשהו של מעברים.

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

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

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

חיות

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

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

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

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

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

חסימות

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

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

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

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

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

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

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

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

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

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

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

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

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

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

הרחבות

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

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

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

• סוגים נוספים של קשתות; שני סוגים נפוצים הם:
  • קשת איפוס (reset arc) אינה מהווה תנאי מקדים של הפעלה, ומרוקנת את המקום כשהמעבר מופעל; זה גורם לנגישות להיות בלתי כריעה^[12], בעוד שתכונות אחרות, כגון סיום, כריעות;^[13]
  • קשת בולמת (inhibitor arc) גורמת לכך שמעבר יכול לפעול רק אם המקום של התנאי המקדים ריק; זה מאפשר לבטא חישובים אקראיים על מספר אסימונים, מה שהופך את הפורמליזם לשלם-טיורינג) ומרמז על קיומה של רשת אוניברסלית^[14].
• ברשתות פטרי סטנדרטיות, לא קיימת הבחנה בין סוגים שונים של אסימונים. ברשת פטרי צבעונית, לכל אסימון יש ערך^[15]. בכלים פופולריים לרשתות פטרי צבעוניות כגון CPN, הערכים של האסימונים מוקלדים, וניתן לבדוק אותם באמצעות תנאי הגנה (guard expressions) ולבצע עליהם מניפולציות באמצעות שפת תכנות פונקציונלית. תת-סוג של רשתות פטרי צבעוניות הוא רשתות פטרי בנויות היטב (well-formed), בהן הקשת ותנאי ההגנה, מוגבלים להקל על ניתוח הרשת.
• הרחבה נוספת של רשתות פטרי היא היררכיה. רשת זו בצורה שונות של מבט תומכת ברמות שונות של מורכבות והפשטה נחקרה על ידי Fehling. צורה שונה של היררכיה נמצאת במה שמכונה רשתות פטרי עצמים (object petri nets) או מערכות עצמים, בהן רשת פטרי יכולה להכיל רשתות פטרי כאסימונים לרבות היררכיה של רשתות פטרי מקוננות שמתקשרות על ידי סנכרון מעברים ברמות שונות. ראה^[16] להצגה בלתי-פורמלית של רשתות פטרי עצמים.
• מערכת הוספת וקטורים עם מצבים (VASS) (ר"ת של Vector Addition System with States) היא פורמליזם שקול לרשתות פטרי. עם זאת, באופן שטחי ניתן לראות בה כהכללה של רשתות פטרי. חשוב על אוטומט סופי כאשר כל מעבר מסומן על ידי מעבר מרשת פטרי. רשת הפטרי אם כן מסונכרנת עם האוטומט הסופי, כלומר מעבר באוטומט מתבצע באותו זמן עם המעבר המקביל ברשת הפטרי. ניתן לבצע מעבר באוטומט רק אם המעבר המקביל ברשת הפטרי מאופשר, ומעבר יכול לפעול ברשת הפטרי אם קיים מעבר מהמצב הנוכחי באוטומט המסומן לפיו. (ההגדרה של VASS בדרך כלל מנוסחת באופן מעט שונה.)
• רשתות פטרי מתעuדפות (Prioritised Petri nets) מוסיפות תכונות למעברים, לפיהן מעבר אינו יכול לפעול אם מעבר בעל עדיפות גבוהה יותר מאופשר (כלומר יכול לפעול). לפיכך, מעברים נמצאים בקבוצות עדיפויות, ולמשל מעברים בקבוצת עדיפות 3 מסוגלים לפעול אם כל המעברים בקבוצות 1 ו-2 כבויים. בתוך קבוצת עדיפות, ההפעלה עודנה לא דטרמיניסטית.
• תכונת אי-הדטרמיניסטיות הייתה יקרת-ערך, משום שהיא מאפשרת למשתמש לפשט מספר רב של תכונות (בהתאם לתכלתית הרשת). במקרים מסוימים, לעומת זאת, הצורך נוצר כדי למדל תזמון, ולא רק את מבנה המודל. למילוי צרכים אלו, התפתחו רשתות פטרי מתוזמנות, בהן ישנם מעברים מתוזמנים, וייתכנו גם מעברים שאינם מתוזמנים (במידה ויש, מעברים שאינם מתוזמנים בעלי עדיפות כבוהה יותר מאלו שכן). תת-קבוצה של רשתות פטרי מתוזמנות היא רשתות פטרי סטוכסטיות המוסיפות זמן לא דטרמיניסטי על ידי אקראיות המעברים הניתנת להתאמה. ההתפלגות המעריכית בדרך כלל משמשת "לתזמון" הרשתות הללו. במקרה זה, גרף הנגישות של הרשת יכול לשמש כשרשרת מרקוב.
• רשת פטרי דואליסטית (dP-Nets) היא הרחבה של רשת פטרי שפותחה על ידי E. Dawis, et al^[17]. על מנת לייצג באופן טוב יותר תהליך בעולם האמיתי. רשתות פטרי דואליסטיות מאזנות את הדואליות של שינוי/חוסר שינוי, אקטיביות/פסיביות, (טרנספורמציה) זמן/מקום, וכו', ומבחינות בין רשתות פטרי המייצגות טרנספורמציה של זמן לכאלו המייצגות טרנספורמציה של מקום. רעיון זה מעניק לרשת פטרי דואליסטית את המאפיין הייחודי שהוא סימון טרנספורמציה, כלומר כשהטרנספורמציה "פועלת" היא מסומנת. זה מאפשר לטרנספורמציה לפעול (או להיות מסומנת) מספר פעמים וכך מתאפשר ייצוג של התנהגות תפוקה של תהליך. סימון הטרנספורמציה מניח כי זמן טרנספורמציה מוכרח להיות גדול מאפס. זמן טרנספורמציה באורך אפס המשמש רשתות פטרי רבות, אמנם מזמין מבחינה מתמטית, אך אינו שימושי בייצוג של תהליכים בעולם האמיתי. רשתות פטרי דואליסטיות גם מנצלות את האבסטרקציה של רשתות פטרי היררכיות, על מנת לתאר ארכיטקטורת תהליך. מערכות תהליכים מורכבות ממודלות כסדרה של רשתות פטרי פשוטות יותר המקושרות ביניהן באמצעות רמות שונות של הפשטה. ארכיטקטורת התהליך של מתג מודגמת ב^[18], שבו דרישות פיתוח מאורגנות סביב מבנה המערכת המתוכננת. רשתות פטרי דואליות מאפשרות למדל, לחקור ולשפר כל תהליך בעולם האמיתי, כגון מערכות מחשוב, תהליכים עסקיים, תעבורה, זרימה, וכו'.

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

הגבלות

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

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

1. באוטומט סופי (SM - state machine), כל מעבר יש קשת נכנסת אחת וקשת יוצאת אחת, וכל הסימונים בעלי אסימון אחד בדיוק. כתוצאה מכך, לא יכולה להיות מקביליות, אך יכול להיוותר קונפליקט (כלומר אי-דטרמיניזם). מתמטית: ${\displaystyle \forall t\in T:|t^{\bullet }|=|{}^{\bullet }t|=1}$
2. בגרף מסומן (MG - marked graph), לכל מקום יש קשת נכנסת אחת וקשת יוצאת אחת. דהינו, לא יכול להיווצר קונפליקט, אך יכולה להיות מקביליות. מתמטית: ${\displaystyle \forall s\in S:|s^{\bullet }|=|{}^{\bullet }s|=1}$
3. ברשת בחירה חופשית (FC - free choice), - כל קשת ממקום למעבר היא הקשת היחידה ממקום זה או הקשת היחידה למעבר זה. כלומר יכולים להתקיים הן מקביליות והן קונפליקט, אך לא באותו הזמן. מתמטית: ${\displaystyle \forall s\in S:(|s^{\bullet }|\leq 1)\vee ({}^{\bullet }(s^{\bullet })=\{s\})}$
4. בחירה חופשית מורחבת (EFC - extended FC) - רשת פטרי שיכולה להפוך ל-FC.
5. ברשת בחירה אסימטרית (AC - Asymmetric choice), מקביליות וקונפליקט (בסיכום, בלבול) יכולים לקרות, אך לא באופן סימטרי. מתמטית: ${\displaystyle \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 })]}$

רשתות זרימה

רשתות זרימה (Workflow nets או בקיצור WF-nets) הן תת-קבוצה של רשתות פטרי שמטרתן למדל את זרימת פעילויות התהליך^[19]. המעברים ברשת זרימה מוקצים עבור משימות או פעילויות, ומקומות מוקצים לתנאי קדם או תנאים אוחרים. לרשתות הזרימה ישנן דרישות מבניות ופעולה נוספות, בעיקר התוספת של מקום קלט יחיד (מקור - source) ללא מעברים קודמים, ומקום פלט (בור - sink) ללא מעברים עוקבים. בהתאם לכך, ניתן להגדיר סימוני התחלה וסוף המייצגים את סטטוס התהליך.

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

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

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

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

רשת זרימה מתוחזקת היטב עם איטרציה רגילה (WRI - well-handled with regular iteration) היא רשת זרימה מורחבת לא מעגלית. רשת זרימה WRI יכולה להיבנות כצירוף של רשתות, כלומר החלפת מעבר ברשת זרימה WRI בתת-רשת זרימה WRI. התוצאה תהיה גם רשת רשת זרימה WRI. רשתות זרימה WRI הן גם נאותות-G^[21], לכן על ידי שימוש באבני בניין מסוג רשת זרימה WRI בלבד, ניתן להשיג רשתות זרימה שהן נאותות-G לפי המבנה.

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

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

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

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

תחומי יישום

• 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. Vol. 9. pp. 223–252. doi:10.1145/356698.356702.
• Peterson, James Lyle (1981). Petri Net Theory and the Modeling of Systems. Prentice Hall. ISBN 0-13-661983-5.
• Petri, Carl A. (1962). Kommunikation mit Automaten (תיזה). University of Bonn.
• 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.
• 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.

קישורים חיצוניים

מדיה וקבצים בנושא רשת פטרי בוויקישיתוף

• Petri, Carl Adam; Reisig, Wolfgang. "Petri net". Scholarpedia. p. 6477. doi:10.4249/scholarpedia.6477. נבדק ב-2008-07-13.
• 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. אורכב מ-המקור (PDF) ב-2013-07-27. נבדק ב-2015-07-10.
• 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.

הערות שוליים

1. Petri, Carl Adam; Reisig, Wolfgang (2008). "Petri net". Scholarpedia. p. 6477. doi:10.4249/scholarpedia.6477.
2. Rozenburg, G.; Engelfriet, J. (1998). "Elementary Net Systems". In Reisig, W.; Rozenberg, G. (eds.). Lectures on Petri Nets I: Basic Models - Advances in Petri Nets. Lecture Notes in Computer Science. Vol. 1491. Springer. pp. 12–121.
3. Reisig, Wolfgang (1991). "Petri Nets and Algebraic Specifications". Theoretical Computer Science. 80 (1): 1–34. doi:10.1016/0304-3975(91)90203-e.
4. Desel, Jörg; Juhás, Gabriel (2001). "What Is a Petri Net? Informal Answers for the Informed Reader". In Ehrig, Hartmut (ed.). Unifying Petri Nets. LNCS. Vol. 2128. Springerlink.com. pp. 1–25. נבדק ב-2014-05-14.(הקישור אינו פעיל)
5. Esparza, Javier; Nielsen, Mogens (1995) [1994]. "Decidability issues for Petri nets - a survey". Bulletin of the EATCS (Revised ed.). נבדק ב-2014-05-14.
6. Lipton, R. (1976). "The Reachability Problem Requires Exponential Space". Technical Report 62. Yale University.
7. Küngas, P. (ביולי 26–29, 2005). Petri Net Reachability Checking Is Polynomial with Optimal Abstraction Hierarchies. Proceedings of the 6th International Symposium on Abstraction, Reformulation and Approximation—SARA 2005. Airth Castle, Scotland, UK. אורכב מ-המקור ב-2012-02-09. נבדק ב-2015-07-10.
8. Murata, Tadao (באפריל 1989). "Petri Nets: Properties, Analysis and Applications". Proceedings of the IEEE. pp. 541–558. doi:10.1109/5.24143. נבדק ב-2014-10-13.
9. "Petri Nets". www.techfak.uni-bielefeld.de.
10. David, René; Alla, Hassane (2005). Discrete, continuous, and hybrid Petri Nets. Springer. ISBN 978-3-540-22480-8.
11. Jensen, Kurt. "A brief introduction to colored Petri nets" (PDF). אורכב מ-המקור (PDF) ב-2005-03-13. נבדק ב-2015-07-10.
12. Araki, T.; Kasami, T. (1977). "Some Decision Problems Related to the Reachability Problem for Petri Nets". Theoretical Computer Science. 3 (1): 85–104. doi:10.1016/0304-3975(76)90067-0.
13. Dufourd, C.; Finkel, A.; Schnoebelen, Ph. (1998). "Reset Nets Between Decidability and Undecidability". Proceedings of the 25th International Colloquium on Automata, Languages and Programming. LNCS. Vol. 1443. pp. 103–115.
14. Zaitsev, D. A. (2013). "Toward the Minimal Universal Petri Net". IEEE Transactions on Systems, Man, and Cybernetics: Systems. 44: 1–12. doi:10.1109/TSMC.2012.2237549.
15. "Very Brief Introduction to CP-nets". Department of Computer Science, University of Aarhus, Denmark. אורכב מ-המקור ב-2010-10-28. נבדק ב-2015-07-10.
16. http://llpn.com/OPNs.html
17. Dawis, E. P.; Dawis, J. F.; Koo, Wei-Pin (2001). Architecture of Computer-based Systems using Dualistic Petri Nets. 2001 IEEE International Conference on Systems, Man, and Cybernetics. Vol. 3. pp. 1554–1558.
18. Dawis, E. P. (2001). Architecture of an SS7 Protocol Stack on a Broadband Switch Platform using Dualistic Petri Nets. 2001 IEEE Pacific Rim Conference on Communications, Computers and signal Processing. Vol. 1. pp. 323–326.
19. van der Aalst, W. M. P. (1998). "The application of Petri nets to workflow management" (PDF). J of Circuits, Sys and Comput. pp. 21–66. doi:10.1142/s0218126698000043. אורכב מ-המקור (PDF) ב-2016-11-19. נבדק ב-2015-07-10.
20. van Hee, K.; Sidorova, N.; Voorhoeve, M. (2003). "Soundness and separability of workflow nets in the stepwise refinement approach" (PDF). In van der Aalst, W. M. P.; Best, E. (eds.). Application and Theory of Petri Nets 2003. Lect Notes in Comput Sci. Vol. 2678. Springer. pp. 337–356.
21. Ping, L.; Hao, H.; Jian, L. (2004). Moldt, Daniel (ed.). On 1-soundness and soundness of workflow nets. Proc of the 3rd Workshop on Modelling of Objects, Components, and Agents. Vol. 571. Aarhus, Denmark: DAIMI PB. pp. 21–36.
22. Karniel, A.; Reich, Y. (במאי 2011). "Formalizing a Workflow net implementation of Design-Structure-Matrix-based Process Planning for New Product Development". IEEE Transactions on Systems, Man, and Cybernetics--Part A: Systems and Humans. pp. 476–491. doi:10.1109/tsmca.2010.2091954.
23. Mazurkiewicz, Antoni (1995). "Introduction to Trace Theory". In Diekert, V.; Rozenberg, G. (eds.). The Book of Traces. Singapore: World Scientific. pp. 3–67.
24. Winskel, G.; Nielsen, M. "Models for Concurrency" (PDF). Handbook of Logic and the Foundations of Computer Science. Vol. 4. OUP. pp. 1–148.