FormModZH2Ossz

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Elmélet

1.

Petri hálók diagnosztikai alkalmazásában a háló milyen (strukturális/dinamikus) tulajdonságát használjuk fel a megoldások keresésében és milyen a hipotézisekre vonatkozó konzisztencia kritériumokat alkalmazunk?
A T-invariánsokkal maszatolunk, de hogy itt konkrétan milyen tulajdonságokra gondol, az jó kérdés. A konzisztencia kritérium azt jelenti, hogy csak azokat a hipotéziseket fogadhatjuk el, amelyek konzisztensek a megfigyeléseinkkel. Kétféle diagnózis van, a konzisztencia bázisú, illetve az abduktív. Konzisztenciabázisúnál csak az a követelmény, hogy a hipotézisből ne következzen semmi olyan, ami a megfigyeléseinkkel ellentétes, míg abduktívnál a hipotézisből direktben következnie kell mindennek, amit megfigyeltünk. Vagyis kétféle konzisztencia feltétel van (Ψ⁺ és Ψ^- halmazok), az egyikre abduktív, a másikra konzisztencia bázisú a követelmény.

2.

Színezett Petri hálókban értelmezhetjük-e a T-invariáns fogalmát? Ha igen, mi a különbség a színezetlen Petri hálókhoz képest? Ha nem, mi az elvi szabály?
Igen, értelmezhetjük. Hogy mi a különbség? Rendes PN-ben tudjuk mi a T-invariáns. Színezettben ezzel szemben:

Ezen a helyen volt linkelve a t-inv.PNG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

3.

Petri hálónál ismétlődés (ismételhetőség) statikus v. dinamikus tulajdonság? Mi a (részleges) ismételhetőség feltétele, hogyan fejezhető ki a szomszédossági mátrixszal? (2p)
Statikus. Egy N Petri háló (részlegesen) ismételhető, ha létezik olyan M₀ kezdőállapot és M₀-ből induló σ tüzelési szekvencia, hogy minden (néhány) t ∈ T tranzíció végtelen sokszor tüzel σ-ban

4.

Mi a színezett Petri hálóban az őrfeltétel definíciója? A CPN mely eleméhez kapcsolódnak, hogyan értékelhetők ki, hogyan befolyásolják a háló működését? (2p)
Az őrfeltételek, vagy angol nevükön guard kifejezések a tranzíciókhoz tartozó, multi-halmazokon értelmezett logikai kifejezések. Az őrfeltétel nem teljesülése (a logikikai kifejezés kiértékelésekor kapott hamis eredmény) az adott tranzíció engedélyezettségének megvonását eredményezi. Kiértékeléskor a nyílt kifejezésben szerepló változókat a bemenő helyeken levő tokenek segítségével az összes lehetséges módon lekötjük, majd ezeket kiértékeljük, ha valamelyik lekötéssel az őrfeltétel igazzá válik, a tranzíció engedélyezetté válhat az adott lekötéssel.

5.

Mit tudunk egy korlátos Petri háló P- és T-invariánsairól?
Úgy véljük, semmit. Íme egy példa KÉP, ami korlátos és nincs neki se P se T invariánsa. Ugyanakkor másik példa is adható, aminek meg van P és T invariánsa, és korlátos.

6.

Mit jelent a Petri háló alosztályok kapcsán definiált asszimetrikus konfúzió fogalma?
Konfúzió: konkurens és konfliktusos. Asszimetrikus konfúzió: tüzelési szekvenciától függ, hogy konkurens és konfliktusos-e.

7.

Definiálható-e a színezett Petri hálókra az invariánsok fogalma? Ha igen, hogyan? Ha nem, miért nem?
Hát nyilván igen, mert vannak a slideokon, meghát ha kiterítjük sima PNné arra értelmezhető, akkor nyilván az eredeti szinesben is kell megfelelője legyen. De a hogyanra nem nagyon volt semmi irva. Annyi hogy hasonlóan mint a programok invariánsai (??) és a P-invre volt néhány példa hogy a M(P1)+M(P2)..... = token vagy tokenhalmaz. Annyi nehézséget jelent a T invariáns, hogy az azonos szinű tokenek még lehetnek különbözőek, ha az attribútumaik különböznek, míg a fekete-fehér PN-nél ez nem volt gond.

8.

Milyen kapcsolatban van egymással a Petri hálók élő és deadlock-mentes tulajdonsága?
L4 élő == élő => deadlock-mentes.

9.

Számítási komplexitás szempontjából melyik analízis módszer rendelkezik kedvezőbb tulajdonságokkal és miért: az elérhetőségi analízis vagy az invariáns analízis?
Elérhetőőség: exponenciális, invariáns: $O(n^{2})$ -es, tehát az invariáns

10.

A Petri hálók diagnosztikai alkalmazása melyik analízis módszeren alapul és miért pont azon?
A hibaterjedési mechanizmusokat (hiba, hibaállapot, szindróma) vizsgáljuk, és ehhez a T invariánsokra van szükség.

=Igaz/Hamis

Igaz/ Hamis?	Kérdés	Magyarázat
Igaz	Ha egy PN biztos akkor egyúttal korlátos is..	Az egy korlátos PN-t nevezzük biztosnak.
Igaz	Ha egy PN megfordítható akkor tetszőleges M eleme R(N,M0) állapot visszatérő..
Igaz	Perzisztens PN-ben egy engedélyezett átmenet mindaddig engedélyezett marad, amíg nem tüzel..
Igaz	Ha egy PN élő akkor nincs benne olyan (nem izolált) hely amelyben egyetlen állapotban sincs token.
Igaz	Egy rendszer elérhetőségi gráfjának és fedési gráfjának topológiája csak akkor nem azonos, ha az w (omega) megjelenik állapotcímkeként.
Igaz	Ha egy tranzíció L3 élő akkor L2 élő és L1 élő is.
Igaz	A prioritás megőrzi a szinteken belüli nemdeterminizmust.
Igaz	Ha egy Petri háló megfordítható, akkor biztosan van legalább egy L3-élő tüzelése.
Igaz	Ha egy (N, M0) állapotgép élő, akkor N biztosan erősen (szigorúan) összefüggő, és M0-ban van legalább egy token.
Igaz	Az elérhetőségi gráfban (w) omega akkor jelenik meg címkeként, ha a tokenek száma minden határon túl nőni kezd.
Igaz	Az elérhetőségi gráf szélességi típusú bejárása a tranzíciók tüzelése mentén építi fel az állapotteret.
Igaz	Véges kapacitású Petri háló átalakítható kapacitáskorlát nélküli Petri hálóvá.	Az adminisztratív helyek bevezetésével.

Igaz	Nem korlátos Petri-hálóban nem létezhet minden helyet lefedő P-invariáns.	Ha a token szám a végtelenségig nő, azt akárhogy súlyozzuk, sose lesz annyi, mint a kezdőeloszlásban..
Igaz	Kiegészítő hely-transzformációval megvalósított kapacitáskorlátos hálóban a kapacitásos helyet és a hozzá tartozó adminisztrációs helyet lefedi egy P-invariáns.	Hisz az adminisztratív helyben annyi token van, amennyi felhasználatlan kapacitás, így a két helyben összesen annyi token van, mint az eredeti hely kapacitás korlátja.
Igaz	Ha egy háló L3 élő, akkor van benne L1 élő tranzíció.	Minden tranzíció L3 élő, ami magában foglalja az L1 élőséget is.
Igaz	Ha egy tranzíció halott, akkor nem jelenik meg a háló fedési fájában.
Hamis	Ha egy PN valamelyik állapota fedhető, akkor az már biztosan nem lehet visszatérő állapot.
Hamis	Ha egy helyből csak egy kisebb és egy nagyobb prioritású időzítetlen tranzícióba vezet él, akkor a kisebb prioritású tranzíció sosem lesz engedélyezett.	P. Ha a nagyobb prioritásunak nem teljesülnek az egyéb tüzelési feltételei.
Hamis	A tranzíció engedélyezett, ha létezik legalább egy olyan bemenő él, amelynek súlya nem több, mint az élhez kapcsolódó bemeneti helyen levő tokenek száma.
Hamis	A kimeneti helyek kapacitáskorlátja csak a tüzelés végrehajthatóságában játszik szerepet, az átmenet engedélyezettségében nem.
Hamis	Az elérhetőségi gráfban minden egyes él egyéni címkét kap.
Hamis	Egy élő PN elérhetőségi gráfja minden esetben tartalmaz legalább egy szigorúan összekötött komponenst.
Hamis	Az elérhetőségi gráf önmagában nem alkalmas egy véges állapotú rendszer élőségének bizonyítására. (feltéve, hogy M0 is adott).
Hamis	Ha egy PN L4 élő akkor korlátozottan fair (B-fair) is.	Az élőség nem biztosítja, hogy egy tranzíció valaha tüzelni fog..
Hamis	Ha egy PN-nek adott kezdőállapotból elindítva létezik L3 élő tüzelése akkor az L3 élő.	Az összes tranzíciónak L3 élőnek kell lennie ehhez.
Hamis	Egy élő PN P-invariánsai minden esetben lefedik a háló összes helyét.
Hamis	A prioritási szintek bevezetése a Petri hálókban nem módosítja a tüzelési feltételt.
Hamis	A prioritási szintek fogalma csak színezett Petri hálók esetén értelmezett.
Hamis	A prioritási szintek bevezetése módosíthatja a háló kezdő token eloszlását.
Hamis	Egy forrás vagy nyelő tranzíciót tartalmazó Petri háló csak akkor lehet élő és biztos, ha az elérhetőségi gráfja erősen összefüggő.	forrást és nyelőt ugyanis nem enged meg a szigorú összekötöttség!)
Hamis	Ha egy Petri hálónak van legalább egy L3-élő tüzelése, akkor a háló biztosan L2-élő is.
Hamis	Egy M állapotból kiindulva az elérhetőségi gráfban pontosan annyi rákövetkező csomópont található, amennyi az M állapotban engedélyezett tranzíciók száma.	(Lehet kevesebb is. Mondjuk ha két hely van, egyikből a másikba két különböző nevű tranzíción keresztül is lehet tüzelni. És a kezdőállapotban az első helyen van egy token. Ekkor az elérhetőségi G-ben M0-ből két él vezet a köv (1db) állapotba. tehát: nem pontosan hanem legfeljebb annyi rákövetkező! )
Hamis	Az állapotegyenlet csak az elérhetőségi gráf segítségével oldható meg, és csak exponenciális komplexitású algoritmus létezik hozzá.
Hamis	A prioritásos Petri hálók esetén a tranzakciók tüzelési sorrendje minden esetben determinisztikus.	Prioritási szinteken belül továbbra is nemdeterminisztikus.
Hamis	Erős és gyenge tüzelési szabály közt az a különbség, hogy az erős figyelembe veszi a tranzíciók prioritását, míg a gyenge nem.	Az erős figyelembe veszi a helyek kapacitás korlátait.
Hamis	Véges kapacitású Petri hálóban egy tranzíció mindig tüzelhet, ha az összes bemeneti helyén a bemenő éleknek megfelelő számú token van.	Az erős tüzelési feltétel szerint a kimenő helyek kapacitás korlátaira is figyelni kell.
Hamis	Ha egy hálóban vannak L0 élő (halott) tranzíciók, akkor a hálóban van deadlock.
Hamis	Ha létezik minden állapotot lefedő P-invariáns, akkor a háló nem lehet halott.
	Az állapottérben ciklikus működésű rendszerben biztosan található T-invariáns.
	Egy háló élősége egyértelműen megállapítható pusztán a T-invariánsok alapján.

TODO: powered by OmniPage OCR
Formázást javítottam, a spell check még hátravan -- Peti - 2007.06.26.

1.1-1. Mely állítások igazak a P-invariánsra?

1. Ha a P-invariánsok nem fedik lc háló minden egycs helyet. akkor a háló nem korlátos.
2. Ha egy Petri hálóban a helyek egy reszhalmazában a tokenek száma egy (végtelen)

tüzelési szekvenciában állandó, akkor biztosan létezik berme legalább egy P-invarians.

1. Pusztán a fedési grid- ismeretében nem hatarozhato meg egy Petri hálo minden P-invariánsa.
2. Kizárólag a szomszedossagi matrix ismerete alapjan meghatározhatók a halo P-invariánsai.

pont hamis

1.1-2. Mely állitások igazak az alábbi, korlatossággal, élőségi, illetve deadlockmentességgel kapcsolatos állitások közül? (12 pont)

1. Egy korlatos, éle, visszatérő állapottal rendelkező Petri hálóra igaz,

hogy minden tranziciója tüzelhető valamely visszaterö al lapotban.

1. Ha minden helyre igaz, bogy a szomszedossagi matrixban a hozzá tartozó sorban (esztepban)

az elemek összege 0, akkor a háló korlátos.

1. Egy adott kezdojeloles mellett deadlockmentcs halo L1-élő.
2. Ha egy (N,Mo) Petri haló minden tranzicioja vegtelen sokszor előfordul valamely L(N,Mo)

tüzelési szekvenciaban, akkor biztosan nines benne deadlock.

1.1-3. Mely állítások igazak tranziciók engedélyezettségére, illetve tüzelhetősegére?

1. Egy biztonságos Petri haloban egy tranzicio engedelyezett, ha minden bemeneti helye jelölt.
2. Ha egy helyböl egy kisebb es egy nagyobb prioritise időzítetlen tranzicioba egyarant vezet el,

akkor bármely tokeneloszlas eseten a nagyobb prioritású tranzició tüzel.

1. Ha egy tranzició adott tokeneloszlas esetén engedelyezett, akkor minden ebbol a

tokeneleszlasból tüzelhető tranzíció-szekvenciában a a tranzició tüzelhető.

Korlátosság

Bármely állapotban minden helyen maximum k token lehet. (Kiinduló állapot függő!)

Strukturális korlátosság

Egy N Petri háló strukturálisan korlátos, ha bármely korlátos M0 kezdőállapotra korlátos marad

Bizos Petri Háló

Korlátos, k=1. (Azaz egy helyen vagy 0 vagy 1 token van.)

t átmenet élősége

• L0: t sohasem tüzelhető az adott állapotból kiindulva
• L1: t legalább egyszer tüzelhető valamely M0-ból induló tüzelési szekvenciában
• L2: t legalább k-szor (k ≥ 0) tüzelhető valamely M0-ból induló tüzelési szekvenciában
• L3: t végtelen sokszor tüzelhető valamely M0-ból induló tüzelési szekvenciában
• L4: t L1 élő bármely M0-ból elérhető állapotban.

Petri háló *élősége*

• Lx élő, ha minden átmenete legalább Lx élő.
• Élő, ha L4 élő.
• (élő=>holtpontmentes)
• A PN struktúrálsian élő, ha létezik olyan M₀ kezdőállapota, amelyben (N,M₀) (L₄)-élő.

Jelölt gráf

acsa élő, ha minden G-beli körben van legalább 1 token. Minden jelölt gráf struktúrálisan élő

FC háló

Struktúrálisan élő, ha minden N-beli szifon tartalmaz csapdát.

Petri háló *megfordítható*

A kezdőállapot bármely követő állapotból elérhető.

Petri háló ismételhető

Ha létezik olyan M0 kezdőállapot és M0-ból induló σ tüzelési szekvencia, hogy minden t eleme T tranzíció végtelen sokszor tüzel.

Petri háló részlegesen ismételhető

Ha létezik olyan M0 kezdőállapot és M0-ból induló σ tüzelési szekvencia, hogy valamely t eleme T tranzícióvégtelen sokszor tüzel.

*Visszatérő* állapot

Van olyan, a kezdőállapotból elérhető állapot, amely bármelyőt követő állapotból elérhető.

Fairség

Tüzelési szekvencia *Korlátozott (B) Fair*

• Bármely átmenet maximum korlátos sokszor tüzelhet a másik tüzelése nélkül.
• Struktúrálisan: ha bármely kezdőállapotra B fair

Tüzelési szekvencia *Globálisan Fair*

Ha a szekvencia nem véges, akkor minden átmenet végtelen sokszor szerepel benne.

Holtpont (Deadlock) mentesség

Minden állapotban legalább egy átmenet tüzelhető.

R(N,M)

Az N Petri Háló M állapotából elérhető állapotok.

L(N,M)

Az N Petri Háló M állapotából végrehajtható szekvenciák halmaza.

T-invariáns

A σ tüzelési szekvencia végrehajtása nem változtatja meg a tokeneloszlást

P-invariáns

A μ_P súlyvektor által kijelölt helyeken a tokenek súlyozott összege nem változik.

Szifon Csapda

• szifon:
  

Ezen a helyen volt linkelve a szifon.PNG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

• csapda:
  

Ezen a helyen volt linkelve a csapda.PNG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Alapstruktúra

• Tiszta petri háló: Egy petri hálót tisztának nevezünk, ha nincs benne önhurok, azaz nem fordulhat elő benne, hogy egy p hely valamely t tranzíciónak egyaránt ki- és bemenő helye is.

A Petri hálók dinamikus viselkedése

Tüzelés

• *Engedélyezett tranzíció*:
  • Egy tranzíció tüzelése engedélyezett, ha minden bemenő helyén legalább annyi token van, mint a bemenő helyet és a tranzíciót összekötő él súlya (gyenge tüzelési szabály).
  • Egy engedélyezett t tranzíció tetszése szerint tüzelhet vagy nem tüzelhet (a tüzelés nemdeterminisztikus).
  • Tüzelés során a tranzíció a bemenő helyekről w-(p,t) tokent vesz el, a kimenő helyekre pedig w+(p,t) tokent rak.
  • Véges kapacitású helyek esetén t csak akkor tüzelhet, hogyha egyik p kimenő helyén sem haladná meg a tokenek száma a kapacitáskorlátot (erős tüzelési szabály).

A tüzelés algebrai jellemzése

• Szomszédossági mátrix W = |w(t,p)|| (mérete: ||T|| x ||P)

w(t,p): azt mondja meg, hogy a t. tranzíció tüzelése mennyivel változtatja meg a p helyen lévő tokenszámot (az elvett és hozzáadott tokenek előjeles összege). Az M állapotból a Petri háló a t. tranzíció tüzelésére a következő állapotba megy át: M’ = M + WTet

PN-ben(ahol engedélyezett az önhurok), ott a szomszédsági mátrix értelemszerűen "csal", hisz nem mutatja az önhurok dolgait. 

Tüzelési szekvencia

Kiegészítő helytranszformáció Kapacitáskorlát nélküli petri hálóval modellez véges kapacitáskorlátú petri hálót. Minden p helyhez felvesz egy p’ helyet, ami a még ki nem használt kapacitását adminisztrálja.

Tüzelési szám

Tüzelési szám A tüzelési szám vektor egy tüzelési szekvencia egyes tranzícióinak előfordulási számait adja meg. Egy ti tranzíció X(ti) tüzelési száma a vektor i-edik eleme.

Állapotegyenlet

Állapotegyenlet Egy tiszta petri háló állapotegyenlete: M0 – Mn = WT

A tüzelési szemantika módosítása

• *Prioritás*: Prioritásos esetben egy t tranzíció akkor tüzelhet, ha engedélyezett és nincs az ő prioritásánál nagyobb prioritású engedélyezett tranzíció
• kapacitáskorlát
• *tiltó élek*: Ha egy tranzícióhoz valamely bemenő helyről tiltó él kapcsolódik, akkor a tranzíció nem tüzelhet, ha a bemenő helyen a tiltó él kapacitásánál több vagy egyenlő token van.

=Prioritás

Egy prioritási szinten belül az aktivizálandó tüzelés kiválasztása kötött sorrendben történik.	*HAMIS*	Nem, mert nemdeterminisztikusan
Egy adott token eloszlás esetén az engedélyezett átmenetek között levő feleakkora prioritású átmenetek feleakkora valószínűséggel tüzelhetnek, mint a náluk kétszer akkora prioritással rendelkező engedélyezett átmenetek.	*HAMIS*	Előbb a magasabb prioritásúak tüzelnek, csak utána az alacsonyabbak.
Ha egy helyből egy kisebb és egy nagyobb prioritású időzítetlen tranzícióba egyaránt vezet él, akkor nincs olyan tüzelési szekvencia, amelyben a kisebb prioritású tranzíció tüzelése megelőzi a nagyobb prioritású tranzíció tüzelését.	*HAMIS*	Nem biztos, hogy egyszerre lesznek engedélyezettek, így a kisebb prioritású lehet akkor is engedélyezett, amikor a nagyobb prioritású nem az.

Párhuzamos tevékenységek

• *Konfliktus*: két eseményt, E1-et és E2-t konfliktusban levőnek nevezünk, ha legfeljebb egyikük következhet be
• *Konkurens*: két eseményt konkurensnek nevezünk, ha tetszőleges sorrendben bekövetkezhetnek, konfliktusmentesen
• *Konfúzió*: azon szituációkat, amikben a konfliktus és konkurencia egyidejűleg jelenik meg konfúziónak nevezzük
  • *Szimmetrikus konfúzió*: egyaránt konkurens és konfliktusos, pl ábra szerint t1 és t2 konkurens, mindkettõ konfliktusban van t3 átmenettel
  • *Aszimmetrikus konfúzió*: tüzelési szekvenciától függõen, pl, az ábra szerint t4 és t5 konkurens, de ha t5 tüzel elõbb, akkor t4 konfliktusba kerül t6 átmenettel

=Igaz hamis

Jellegzetes alkalmazásai	Minden helyhez még egy adminisztrációs helyet és egy korlátozó tranzíciót veszünk fel, tiltó élekkel összekötve	*HAMIS*	Minden helyhez csak egy adminisztrációs helyet veszünk fel. Korlátozó tranzícióról szó sincs...
Minden tranzícióhoz rendelünk egy adminisztrációs helyet	*HAMIS*	helyesen: "minden helyhez..."
A létrejövő társháló és az eredeti háló gyenge tüzelési szabályt feltételezve azonos tüzelési szekvenciát produkál	*HAMIS*	Az eredeti háló erős és a társháló gyenge tüzelési szabályát feltételezve lesznek azonosak a tüzelési szekvenciák
Egy adminisztrációs hely kezdőállapota a (hozzátartozó) korlátozott kapacitású hely kihasználatlan kapacitása	*IGAZ*	így inicializáljuk a társhálót.

Elérhetőségi gráf

A petri háló által modellezett rendszer teljes állapotgráfjának megfelelője, gyökere az M0 kiinduló állapot és minden egyes él egy tranzíció tüzelésének felel meg (a csomópontok a tokeneloszlás állapotok)

Analitikusan vizsgálható Petri háló alosztályok

Állapotgép (SM - State Maschine)

Véges állapotú gép (Finite State Machine) Olyan petri háló, amiben minden tranzíció egy bemenő és egy kimenő helyhez kapcsolódik. van konfliktus, de nincs szinkronizáció

Jelölt gráf (MG - Marked Graph)

Egy jelölt gráf egy olyan rendes petri háló mely minden egyes P helyének pontosan egy be és kimenő tranzíciója van van szinkronizáció, de nincs konfliktus

Szabad választású Petri háló (FC - ?)

Egy szabad választású petriháló (FC) olyan rendes petriháló, hogy bármely helyéről minden kiinduló él vagy az adott helyről kiinduló egyetlen kimenő él, vagy egy tranzíció egyetlen bemenő éle  van konkurencia és konfliktus, de nincs egyszerre kettő.(azaz nincs konfúzió)  dekomponálható FSM, és MG komponensekre EFC: lehet többszörös szinkronizáció(lásd ábra lentebb)

Asszimmetrikus választású Petri háló (AC - ?)

): Az aszimmetrikus választású petri háló (AC) egy olyan petri háló, hogy minden p1,p2 helypárosra, ha p1-nek és p2-nek vannak közös leszármazottai (ugyanaz a tranzakció mindkettőtől vesz tokent), akkor p1 leszármazottai részhalmaza p2 leszármazottainak, vagy fordítva.

SM és MG tételek

1. Egy ( N, M0) állapotgép a.cs.a. élõ, ha N erõsenösszefüggõ és M0-ban van legalább egy token

• • triviális, hiszen minden tüzelés csak egy tokent mozgat

1. Egy ( N, M0) állapotgép a.cs.a. biztos, ha M0-ban van legfeljebb egy token
2. Egy élõ ( N, M0) állapotgép a.cs.a. biztos, ha M0-ban pontosan egy token van
3. Egy ( G, M0) jelölt gráfban a tokenek száma minden C irányított körben állandó

• • közönséges Petri háló: egyszeres élek; a körben minden csomóponthoz egy bemenõ és egy kimenõ él

1. Egy ( G, M0) jelölt gráf a.cs.a. élõ, ha M0 állapotban minden G-beli irányított körben van legalább egy token
2. Egy ( G, M0) jelölt gráfban egy élt jelölõ tokenek maximális száma egyenlõ az élt tartalmazó irányított körön az M0 állapotban levõ tokenek minimális számával
3. Egy élõ ( G, M0) jelölt gráf a.cs.a. biztos, ha minden él (hely) olyan C irányított körben van, amelyre M0( C) = 1
4. Egy G irányított gráfban a.cs.a. létezik élõ és biztos jelölt gráfot létrehozó M0 állapot, ha G erõsen összefüggõ gráf

• • a feltétel triviálisan szükséges
  • elégséges is, hiszen van legalább egy irányított kör, és minden irányított körbe elég egy tokent tenni
  • Visszacsatoló élhalmaz (Feedback Arc Set, FAS)
    • Egy E’ élhalmaz visszacsatoló élhalmaz, ha elhagyásával a G erõsen összefüggõ gráf irányított kör mentessé válik, azaz a G’ = ( V, E – E’) körmentes
    • minimális FAS: egyetlen valódi részhalmaza sem FAS
    • minimum FAS: egyetlen más FAS sem tartalmaz kevesebb élt

1. Egy erõsen összekötött élõ ( G, M0) jelölt gráf a.cs.a. biztos, ha az M0 kezdõállapotból elérhetõ minden M∈ R( G, M0) állapotban a jelölt élek halmaza minimális visszacsatoló élhalmaz
2. Egy ( N, M0) szabad választású háló a.cs.a. élõ, ha minden N–beli szifon (lsd.KÉP) tartalmaz jelölt csapdát (lsd.KÉP)
3. Egy élõ ( N, M0) szabad választású háló a.cs.a. biztos, ha N lefedhetõ egy tokent
4. Ha ( N, M0) élõ és biztos szabad választású háló, akkor N lefedhetõ erõsen összekötött MG komponensekkel. Létezik olyan M∈ R( N, M0), hogy minden ( N1, M1) komponens élõ és biztos MG háló, ahol M1 az N1-re vett rész tokeneloszlás

Strukurális tulajdonságok

Struktúrális tulajdonságok azok, amelyek kizárólag a Petri háló topológiájától függenek, de nem függenek annak kezdeti M0 kezdőállapotától.

Strukturális élőség

Egy Petri háló akkor struktúrálisan élő, hogyha létezik olyan M0 kezdeti állapota, amely élő.

Vezérelhetőség

Egy PN, akkor teljesen vezérelhető, hogyha tetszőleges állapota elérhető tetszőleges más állapotából.

Strukturális korlátosság

Egy Petri hálót akkor nevezünk strukturálisan korlátosnak, hogyha tetszőleges kezdőállapota esetén korlátos.

Konzervatívság

egy PN (részlegesen) konzervatív, ha létezik egy olyan y(p) pozitív egész minden egyes (valamely) p helyére, hogy a tokenek súlyozott összege konstans és minden kezdő tokeneloszlésra.

Ismétlődés

Ismétlődés Egy petri hálót (részlegesen) ismételhetőnek nevezünk, ha létezik egy olyan M0 kezdőállapota, és tüzelési szekvenciája, hogy minden tranzíció végtelen gyakran előfordul ebben a tüzelési szekvenciában

Konzisztencia

Egy petri hálót (részlegesen) konzisztensnek nevezünk, ha van egy olyan M0 jelölés és egy olyan tüzelési szekvencia, amely M0-ból visszavezet M0-ba, hogy minden (egyes) tüzelés legalább egyszer ebben a szekvenciában előfordul.

Invariánsok és alkalmazásaik

T-invariánsok

WT %T = 0 A %T tüzelési szekvencia nem változtatja meg a tokeneloszlást. Emiatt ciklus lesz az állapottérben.  ha egy PN élő, akkor létezik benne olyan tüzelési szekvencia amely T invariáns, és minden tranzíciót tartalmaz legalább egyszer. (ha nincs ilyen, nem élő a PN.)

P-invariánsok

W %P = 0 a %P által kijelölt helyeken a tokenek (súlyozott) száma nem változik, azaz a tokenek a helyek egy részhalmazában keringenek

Az invariánsok meghatározása

Nyilvánvaló módon akár a T akár a P-invariánsok egy-egy lineáris vektorteret alkotnak, hiszen az invariánsok tetszőleges lineáris kombinációja maga is egy invariáns lesz.

Alkalmazások

Predikátumok vizsgálata Invariánsokkal.

=T-invariáns

A T invariáns azt mutatja meg, hogy a rendszerben nem fogynak el a tokenek a működés során:	HAMIS	a fenti tulajdonság a P invariánsra jellemző! A T invariánsok a rendszer egyes részeinek ciklikus működésének lehetőségét jelöli meg. Ettől még azonban lehetséges olyan működési mód akár ugyanezen részrendszerre, hogy a tokenek bizony elfogynak frankón!
Ciklikus működésű rendszerben mindenképp van T invariáns.	IGAZ	a T inv. Definíciójából adódik.
Egy T invariáns nem lehet minimális, ha létezik egy másik T invariáns, ami ugyanannyi tranzíciót tartalmaz.	HAMIS	Létezhet másik, azonos részhalmazú T invariáns is a rendszerben, de annak tüzelési számai nem lehetnek kisebbek.

=P-invariáns

Ha egy PN van konzervatív komponens, akkor ebből még nem következik, hogy létezik benne P invariáns.	HAMIS	Egy PN (részlegesen) konzervatív, ha van benne P inv. .
Ha egy WT %; szomszédossági mátrixszal rendelkező PN létezik olyan %T súlyvektor hogy legalább egy token eloszlásra igyaz az összefüggés: W%T = 0 akkor a %T súlyvektort hely invariánsnak nevezzük.	HAMIS	minden a kezdőállapotból elérhető eloszlásra teljesülnie kell a fenti egyenlőségnek.ahhoz, hogy P invariánsnak hívhasuk
A P invariáns segít annak ellenőrzésében, hogy a modellezett rendszerben lévő folyamatok megfelelően kapcsolódnak-e az általuk használt erőforrásokhoz.	IGAZ	a P invariáns azt mutatja+, hogy a rendszerben az erőforrások nem fogynak el a működés során és így jól használható pl. hozzáférési protokollok helyességének bizonyításában.
Nem véges elérhetőségi gráffal rendelkező rendszerben csak akkor van P invariáns, ha van ciklikus működésű komponense.	HAMIS	lehet olyan rendszert találni, amiben nincs T invariáns, de tutkón van P invariáns.

=Alkalmazások_v

Ha egy negálatlan klózrendszer megoldható (kielégíthető), akkor PN modelljében egy T invariánsnak megfelelő tüzelési szekvencia végrehajtható.	*IGAZ*	A model kialakítása úgy történt, hogy a klózrendszer megoldása egy olyan tüzelési szekvenciának feleljen meg, ami T invariáns.
T invariánsokka tetszőleges, negálatlan elsőrendű logikai formulákból álló rendszert analizálhatunk.	*IGAZ*	Lásd jegyzet.
Egy logikai program Petri hálós modelljében a P és T invariánsok megegyeznek.	*HAMIS*	A P invariánsokról szó se volt :)
Murata algoritmus negálásmentes klózok esetén Tinvariánsokra, negált klózokat tartalmazó logikai program esetén P invariánsokra működik.	*HAMIS*	A Murata algoritmus működésének feltétele, hogy a klózrendszer negálatlan legyen.

*Jól formált petri háló*

• színezettek, és a számosságot a színekkel fejezik ki.
• reguláris hálózatok esetén lehetővé teszik szimbolikus elérhetőségi gráfok megalkotását
• jól formált PN megközelítésének alapgondolata, hogy a kezelhetőség érdekében az alkalmazható színezést és tüzelési szabályokat korlátozza, és a komplex kifejezéseket agy jól körülhatárolt szabályrendszerben a garantáltan analizálható struktúrákra szorítja meg.
• tetszőleges szín esetén a hálózat működésének szimmetrikusan azonosnak kell lennie.