Petri ağı

Bir Petri ağı (yer/geçiş ağı, yerleşim/geçiş ağı veya Y/G ağı olarak da bilinir) sistemlerin incelenmesi için kullanılabilecek bir araçtır. Petri ağları, sistemin matematiksel bir modelle modellenebilmesine izin verir. Bir Petri ağı, geçiş ve yerleşim düğümlerinden oluşan tek yönlü iki parçalı graf olarak da tanımlanabilir. Ok şeklinde gösterilen yönlü eğriler, bir geçişten önce ve sonra hangi yerlerin olduğunu tanımlarlar.
Bazı kaynaklar Petri ağlarının 1939 Ağustos'unda, henüz 13 yaşında olan Carl Adam Petri tarafından, kimyasal prosesleri tarif etmek amacıyla bulunduğunu belirtirler.
Petri ağları, UML, BPMN ve EPC gibi endüstri standartlarına benzer şekilde seçim, tekrarlama, eşzamanlı çalışma gerektiren adımlı prosesler için bir grafiksel notasyon sunar. Ancak bu standartların ötesinde, proses analizi için geliştirilmiş matematiksel teorisiyle ilgili proseslerin çalışmasını matematiksel bir kesinlikte modelleyebilir.

Petri ağ temelleri

Bir petri ağı yerler, geçişler ve eğrilerden oluşur. Yerler ve geçişler, graf teorisindeki düğümler ve kenarlar ile eşdeğerdir. Eğriler bir yerden bir geçişe veya bir geçişten bir yere doğru koşarlar. İki yer arasında veya iki geçiş arasında bir eğri olamaz. Geçişe giriş yapan eğri hangi yerden çıkış yaptıysa, bu yere geçişin giriş yeri; Geçişten çıkış yapan eğri hangi yere giriş yaptıysa, bu yere geçişin çıkış yeri denir.
Grafiksel olarak bir Petri ağındaki bir yer ayrık sayıdaki işaretler içerebilir. Bu işaretler jeton olarak adlandırılır. Jetonların herhangi bir anda yerler üzerindeki dağılımı işaretleme, jeton dağılımı veya konfigürasyon olarak adlandırılır.
Bir geçişin giriş yerlerinde yeterli jeton var ise, bu geçiş etkinleştirilmiş veya tetiklenebilir denir.
Etkinleştirilmiş bir diğer ifade ile, tetiklenebilir bir geçiş tetiklendiğinde, giriş yerlerinden ihtiyaç duyulan miktarda jeton tüketir ve çıkış yerlerinde üretilmesi gereken miktarda jeton üretilir. Bu 'gereken' miktarlar, ilgili geçişin ağırlığı, ayrık sistemler için özelleştirirsek geçişin üzerinde yazan rakam, ile gösterilir.
Tetikleme atomiktir. Yani anlık olarak, tek bir seferde gerçekleşir ve yarıda bırakılamaz.
Bir çalışma kuralı tanımlanmadığı sürece, Petri ağlarının çalışması nondeterministictir: Aynı anda birden fazla geçiş tetiklendiğinde, hangisinin tetikleneceği bilinemez ya da bir başka deyişle, geçişlerin herhangi birisi tetiklenebilir.
Tetikleme deterministik olmadığından ve ağda herhangi bir yerde birden fazla sayıda jeton bulunabileceğinden, Petri ağları dağıtılmış sistemlerin eşzamanlı davranışını modellemek için uygundur.

Bir adımda ulaşılabilirlik

Eğer  ise, M işaretlemesinden bir adımda  işaretlemesine ulaşılabilir deriz. (Ya da  , M'den bir adımda ulaşılabilirdir)

Ulaşılabilirlik

'nin 'nin reflexive transitive closure'u olduğu durumlarda ;   ise, herhangi bir adım sayısında ulaşılabiliyorsa,  , M 'den ulaşılabilirdir deriz.
, işaretli bir Petri ağı olmak üzere,   ilk işaretlemesinden itibaren gerçekleştirilebilecek ateşemelerle(tetiklemelerle) ilgileniriz. Bu, ulaşılabiir işaretlemeler kümesidir ve şeklinde gösterilir.

Ulaşılabilirlik grafı

N'nin ulaşılabilirlik grafı , onun ulaşılabilir işaretlemeleri ile sınırlanmış geçiş ilişkileridir  .  Bu, ağın durum uzayıdır. (özetle, ağın alabileceği tüm durumları gösteren kümedir)
G grafına ve'  'ilk durumuna sahip bir Petri ağındaki ateşleme sekansı (ya da sıralı ateşleme kümesi)'  'ile gösterilir. Öyle ki;'. Burada ateşleme sekanslarının kümesi   ile gösterilmiştir.

Tanımlardaki farklılıklar

Daha önce de belirtildiği gibi, tanım farklılıklarının en genel olanı, eğri ağırlıklarını göz ardı etmek ve W ile gösterilen eğriler multisetini,  ile gösterilen ve akış ilişkisi olarak adlandırılan bir basit küme ile değiştirmektir. Bu ifade gücünü (expressive power) sınırlandırmaz, her ikisi de birbirleri yerine kullanılabilir.
Genel olarak kullanılan bir diğer farklılık da, Desel ve Juhás (2001)'ın da kullandığı üzere, kapasitelerin yerler üzerinde tanımlanmış olmasına izin verilmesidir. Aşağıda ekler bölümünde bu konu tartışılmıştır.