Token definíció

Nagyon gyakran használt az a kiterjesztett modell, amikor megengedjük, hogy a helyek ne csak egy-egy, hanem bármennyi nemnegatív egész számú tokent tartalmazhatnak az egyes helyek egyidejűleg. Ekkor megengedett általában az is, hogy egy tranzíció őse vagy utóda ne csak, mint korábban, egyszeresen legyen az adott tranzícióhoz kötve.

Ekkor súlyozott éleket alkalmazva, az él w súlya azt jelenti, hogy ennyi tokennek kell rajta egyszerre mozognia, vagyis az őshelytől ennyi token szükséges a tranzíció tüzeléséhez, és ennyivel csökken a tokenek száma ott a tüzeléskor, míg az utódhelyre annyi token érkezik, amennyi a tranzíciótól az adott helyre mutató él súlya.

Ennek megfelelően egy tranzíció akkor engedélyezett, ha az őshelyein van elegendő számú token. Ennek következményeként előfordulhatnak olyan tüzelési sorozatok, amelyek egyre több tokent termelnek, és így a tokenek száma nem korlátos a modellben.

Így egy token definíció egy P elemű nemnegatív egész értékeket tartalmazó vektorral írhatunk le legegyszerűbben: a vektor elemeit kölcsönösen egyértelműen feleltetjük meg a helyeknek. A vektor egyes értékei azt jelentik, hogy a hely hány tokennel rendelkezik.

A Petri-hálóhoz általában hozzárendelünk egy kezdeti token-eloszlást, vagyis megadjuk, hogy kezdetben melyik hely mennyi tokennel rendelkezik.

Ekkor a rendszer állapotváltozását a következőképpen adhatjuk meg: válasszunk ki nemdeterminisztikusan egy engedélyezett t tranzíciót. Töröljünk a t minden őshelyéről annyi tokent, amennyi a helyről a tranzícióhoz vezető él súlya, és tegyünk token definíció tokent a t minden egyes utódhelyére, amekkora a token definíció odavezető él súlya.

A tranzíció tüzelése alapján ugyanúgy definiáljuk a tüzelési sorozatokat, mint a bináris Petri-hálók esetén. Amint a definícióból látszik, azzal, hogy egyszerre több tokent is megengedünk egy helyen, a tranzíciók tüzelésének az a feltétele megszűnt, hogy az utódhelyek üresek legyenek.

A későbbiekben látni fogjuk, hogy néha nem árt, ha ilyen jellegű feltételt továbbra is meg tudunk fogalmazni. A továbbiakban, ha egy élhez nem adunk meg súlyt, akkor úgy tekintjük, hogy egységnyi súlyú. Ugyanúgy definiáljuk pl. A lefedési problémát a következőképpen fogalmazhatjuk át token definíció hálókra. Definíció: Legyen adott egy hely-tranzíció háló kezdő token-eloszlással, illetve egy adott token-eloszlás.

Token (egyértelműsítő lap)

A lefedési probléma annak eldöntése, hogy elérhetünk-e a hálóban a kezdő token-eloszlásból olyan token-eloszlást, amely mindenhol legalább annyi tokent tartalmaz, mint amennyi az adott token-eloszlásban van. Token definíció egy a hely-tranzíció hálóknál felmerülő fontos probléma, ami a bináris esetben nem állt fenn: Definíció: A korlátosság problémája: hogy a kezdeti token-eloszlásból elérhető rendszerállapotok száma véges vagy végtelen.

A körmentes Petri-hálók korlátosak. Körmentes hálók esetén az elérhetőségi és egyéb problémák egyszerűen megoldhatóak nemcsak a bináris esetben, hanem hely-tranzíció hálók esetén is.

Mi az a tokenizált (programozható) gazdaság?

Most programok az online keresetekhez mutatunk az élő tulajdonság különböző fokozataira egy hely-tranzíció háló esetén. Példa élő tulajdonság változatai hely-tranzíció hálóban Legyen adott az 5. Az ábrán nem tüntettünk fel súlyokat az éleken, minden élnek egységnyi a súlya. Token definíció a kezdeti 1,0,0 token-eloszlás a harmadik tranzíció segítségével 1,n,0 alakot vehet fel tetszőleges n nemnegatív egészre. Sőt a harmadik tranzíció L3 végtelenül gyakran tüzelő tranzíció, hiszen a végetlenségig tüzelhet.

Ha egyszer mégis a második tranzíció tüzel, az állapotot a 0,n,1 vektor írja le. A második tranzíció L1 potenciálisan tüzelő tranzíció tehát. Ezután viszont már csak a negyedik tranzíció lesz engedélyezve, és legfeljebb n-szer tüzelhet, beállítva a 0,0,1 token-eloszlást, amikor már nincs engedélyezett tranzíció.

Ez alapján a negyedik tranzíció L2 tetszőlegesen gyakran tüzelő tranzíció. A token definíció lehetséges működéseit tekintve vélemények otthonról interneten az is igaz, hogy az első tranzíció L0 halott, mert soha nem lehet megengedett az adott kezdő token-eloszlásból kiindulva.

Az is token definíció, hogy egyik tranzícióra sem igaz erősebb feltétel annál, mint amit leírtunk.

Az előző példában ismertetett hely-tranzíció háló nem korlátos, hiszen a második helyen a tokenek száma minden határon túl nőhet. Van, ahol a korlátosságot mégis megköveteljük, vagy megkövetelhetjük a probléma jellege miatt. Definíció: Legyen adott egy hely-tranzíció háló, egy token definíció token-eloszlás. Biztonságosnak nevezzük a hely-tranzíció hálót, ha nem fordulhat benne elő, hogy egy helyen egynél több token jelenik meg.

A fenti definíció, bár hasonlóságot mutat a bináris Petri-hálókkal abban, hogy itt is bináris vektorokkal leírhatóak lesznek a lehetséges token-eloszlások, mégis kicsit más jellegű.

A bináris hálók esetén ugyanis egy tranzíció nem lehetett engedélyezett, amíg token volt valamelyik utódhelyén, ez a feltétel viszont a hely-tranzíció hálókban, és így ezekben a biztonságos hálókban sem definíció által van tiltva.

Inkább arról van szó, hogy a háló struktúrája és a kezdeti token-eloszlás olyan, aminek következtében nem fordulhat elő az, hogy több token kerüljön valahova, annak ellenére, hogy ez nem lenne tiltva a háló működése közben: Tétel: A biztonságos hely-tranzíció hálók pontosan a kontaktmentes bináris hálókkal egyeznek meg.

A biztonságos hálók fogalmát általánosíthatjuk, ha egynél több, de korlátozott számú token fordulhat elő egyidejűleg egy-egy helyen token definíció rendszerben. Definíció: Adott egy hely-tranzíció háló és hozzá egy kezdő token-eloszlás. Azt mondjuk, hogy a háló k-korlátos, ha nem érhető el benne olyan token-eloszlás, amiben k-nál több token szerepel egy helyen. Azokat a hely-tranzíció hálókat, amelyek k-korlátosak valamely k pozitív egészre, összefoglaló néven korlátosnak nevezzük.

Világos az is, hogy a korlátosság problémájának szoros kapcsolata van a korlátos hálókhoz: pontosan azokban a hely-tranzíció hálókban lesz az elérhető token-eloszlások száma véges, amelyek korlátosak. Most egy algoritmust mutatunk annak eldöntésére, hogy egy háló korlátos-e a megadott kezdő token-eloszlással. Token definíció lefedési gráf elkészítése tulajdonképpen az elérhetőségi fa technikájának egy olyan változata, amely nem korlátos hely-tranzíció hálók esetén is bináris opció szárnyal. Azt, hogy egy helyen akárhány token megjelenhet, az ω jellel szokás jelölni, ami a végtelen, vagy korlátlan tokenszámot jelzi.

Az algoritmus tulajdonképpen egy keresőfával kereső mesterséges intelligenciabeli algoritmus. Tehát induljunk ki a kezdeti token-eloszlásból, legyen ez a gráfunk első csúcsa, és jelöljük, hogy még nem vizsgáltuk. Amíg van a gráfunkban nem vizsgált csúcs, addig tegyük a következőt: Válasszunk egy ilyen csúcsot, és tekintsük a benne leírt Token definíció token-eloszlást. Vegyük sorra az összes olyan tranzíciót, ami engedélyezett ebben a token-eloszlásban. Ha az adott tranzíció eredményeként létrejövő M' token-eloszlás már szerepel a gráfunkban, akkor egyszerűen adjunk egy olyan irányított élt a gráfhoz, ami az éppen vizsgált csúcsból a létrejövő token-eloszlást tartalmazó token definíció vezet.

Legyen ennek az élnek az a tranzíció a címkéje, amit vizsgáltunk. Ellenkező esetben vizsgáljuk meg, hogy a kezdőcsúcsból a vizsgált csúcsba vezető úton van-e olyan csúcs, amelynek M'' címkéjére igaz, hogy a most előállított M' token-eloszlás mindenhol legalább annyi tokent tartalmaz, mint M'' vagyis M' lefedi az M''-tmiközben M' és M'' különböznek. Ekkor minden olyan elemét az M'-nek, ami nagyobb, mint az M'' megfelelő eleme, cseréljük ki az ω jelre. Mivel az M'-ben mindenhol legalább annyi token van, mint M''-ben, nyilvánvalóan az M''-ből induló minden tüzelési sorozat az M'-re is alkalmazható, így a megfelelő helyeken a tokenek száma tetszőlegesen nagyra növelhető.

Az új csúcsot az ily módón keletkezett és esetlegesen módosított M' token-eloszlással vegyük fel a gráfba, ha még nem szerepelt új, még nem vizsgált csúcsként, illetve az éppen vizsgált tranzíció legyen annak az irányított élnek a címkéje, ami a most vizsgált M token-eloszlású címkével ellátott csúcsból az új csúcsba vezet. Végül, ha az éppen vizsgált csúcsra minden lehetséges tranzíciót megvizsgáltunk, legyen ez a csúcs már vizsgált, és folytassuk az algoritmust egy újabb, még nem vizsgált csúcs választásával ha van még ilyen.

Az algoritmus véges sok lépés után véget ér és előállítja a lefedési gráfot. Ha szerepel benne az ω, akkor nem korlátos a vizsgált háló az adott kiinduló token-eloszlással, ha viszont az ω nem szerepel a gráf egyik csúcsának címkéjében sem, akkor korlátos a vizsgált háló. Korlátos esetben az előforduló legnagyobb számérték megadja, hogy a háló milyen értékre k-korlátos. Ha ez maximum 1, akkor biztonságos a háló.

Párhuzamos algoritmusmodellek | Digitális Tankönyvtár

Pontosan azok a tranzíciók halottak, amelyen nem szerepelnek a gráfban egyetlen él címkéjeként sem. Példa egy végtelen sok elérhető token-eloszlású háló Legyen adott az 5. Ekkor a lefedési gráfot a következőképpen állíthatjuk elő: a kezdő token-eloszlás 1,0,0,1ez kerül az első csúcsba. Ez az egyetlen nem vizsgált csúcs és egyetlen tranzíció, az első van engedélyezve. A létrejövő 0,1,0,1 token-eloszlást felvesszük a gráfba új, még nem vizsgált csúcsként. A rendszernek ebben az állapotában a második tranzíció van csak engedélyezve, ennek eredménye a token definíció token-eloszlás.

Ez még nem szerepel a gráfunkban, viszont a kezdő token-eloszlást lefedi, a harmadik helyen pedig több token van, mint ott, így a módosított 1,0,ω,1 token-eloszlást vesszük fel a gráfba. Egyetlen eddig nem vizsgált csúcsunk ez az új csúcs, ami esetén az első és a harmadik tranzíció engedélyezett. Az első tranzíció tüzelésével a 0,1,ω,1 eloszlást kapjuk, ezt felvesszük a gráfba.

A harmadik tranzíció tüzelésének eredménye pedig 0,0,ω,1ezt is felvesszük a gráfba. Most két olyan csúcs van, ami még nem vizsgált. Válasszuk először a 0,1,ω,1 token-eloszlásút.

Tőke (közgazdaságtan)

Csak a bináris opciók valós optonok tranzíció engedélyezett, így a 1,0,ω,1 token-eloszlást token definíció, ami már szerepel a gráfban, így csak egy új éllel jelezzük, hogy innen is oda juthatunk. Az egyetlen még nem vizsgált token definíció, a 0,0,ω,1 token-eloszlású csúcs maradt, ez következik. Itt viszont nincs engedélyezett tranzíció, így újabb csúcs nem áll elő.

Ez alapján azt mondhatjuk, hogy a megadott háló nem korlátos. A lefedési gráf segítségével a lefedési probléma is könnyen megválaszolható. Definíció: Ha egy hely-tranzíció háló minden lehetséges token definíció token-eloszlás esetén korlátos, akkor strukturálisan korlátos.

Könnyen belátható, hogy a konzervatív hálók strukturálisan is korlátosak.

Definíció & Jelentés Token

Egy másik irányú korlátozás, ha nem a struktúrára bízzuk és bizonyítjuk a korlátozást, hanem explicite a definícióban megadjuk, ezzel a hálók egy új fajtáját bevezetve.

A Petri-hálókban a valódi informatikai rendszerekből kiindulva szokás korlátozni a tokenek számát az egyes helyeken, vagyis megadhatjuk minden egyes hely esetén, hogy ott maximálisan mennyi token lehet.

Ez a korlátozás a bináris Petri-hálók esetén triviálisan fennállt. Definíció: Legyen adott egy hely-tranzíció háló, ahol egyes helyekre kapacitáskorlátot adhatunk meg. Legyen, mondjuk, a p helyen ez a megadott érték k.

A hálóban csak olyan tüzelési sorozatok lesznek megengedettek, amik segítségével előálló token-eloszlásokra teljesül, hogy a p helyen k-nál nincs több token. Az ilyen hálókat kapacitásos hálóknak nevezzük.

Ha a háló minden helyére megadunk egy pozitív egész kapacitáskorlátot, akkor azt mondjuk, hogy az egész háló kapacitáskorlátozott, vagy a háló véges kapacitású. Azokat a hálókat, amelyekben csak korlátozottan sok token fordulhat elő a működésük közben mert pl. Minden korlátosan igazságos hely-tranzíció háló globálisan is igazságos.

Token (egyértelműsítő lap) – Wikipédia

A megfordítás, vagyis, hogy a globális igazságosság implikálja a korlátosan igazságosságot, teljesül pl. Az ekvivalencia és a tartalmazás probléma tehát megoldható azon hálókra, amelyekben csak véges sok token-eloszlás jöhet létre. Az általános esetben nem ilyen egyszerű a helyzet; a lehetséges token-eloszlások halmaza általában végtelen, és ennek megfelelően a következő eredmény igaz.

Tétel: Az ekvivalencia és a tartalmazás probléma hely-tranzíció hálók esetén általános esetben algoritmikusan nem megoldható. A tétel bizonyítása bonyolult, Hilbert Ezzel szemben speciális tulajdonságú Petri-hálók esetén jobb lehet a helyzet egyes hely-tranzíció háló típusokra algoritmikusan megoldhatóak ezek a problémák. Redukciós technikák Sokszor használhatóak a hely-tranzíció rendszerek tanulmányozására olyan redukciós lépések, amelyek úgy alakítják át a hálót, hogy az élő tulajdonságok, a korlátosság, illetve a biztonságosság ne változzon meg.

Ezekkel a lépésekkel egyszerűsítve a hálót, könnyebben válaszolhatjuk meg az eredeti hálóra vonatkozó kérdéseket. Most néhány ilyen redukciós átalakítást ismertetünk. Az összevonást ennek az úgynevezett token definíció a törlésével végezzük. Fontos, hogy az első helynek ez a lántranzíció az egyetlen utódhelye a bal oldali részben.