Gráftranszformáció

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.

1.1. Gráftranszformáció definíciója, lógó élek kezelése, mintaillesztés injektivitása, negatív alkalmazási feltételek

A gráftranszformáció gráfok szabály és minta bázisú manipulációját végzi azáltal, hogy a szabályok bal oldalán szereplő minta egy előfordulását kicseréli a szabály jobb oldalán szereplő mintával a szabály alkalmazásakor.

Egy gráftranszformációs szabály alkalmazása egy M modellt áttranszformál egy M’ modellbe, azáltal, hogy a baloldali minta egy előfordulását kicseréli a jobboldali minta egy előfordulására. Ez a következőképp zajlik: 1. Gráfmintaillesztés. Megkeressük a baloldali gráfminta egy illeszkedését az M modellben. E lépés magában foglalja a negatív alkalmazási feltételek és az attribútum feltételek ellenőrzését is. 2. Törlés. Az M modell mindazon elemeit letöröljük, melyek illeszkednek a szabály bal oldalához, de nem illeszkednek a szabály jobb oldalához. 3. Létrehozás/Ragasztás. Új objektumokat és kapcsolatokat hozunk létre az M modellben mindazon szabály elemek számára, melyek a jobb oldalon jelen vannak, de a bal oldalon nem. (Elvileg ez az injektív mintaillesztés, de sehol nem találom rendesen leírva)

A negatív alkalmazási feltételek ugyan olyanok, mint a szabály bal oldala, azaz az illesztendő gráf, csak ezek megléte a transzformáció tiltását vonja maga után, hiánya pedig engedélyezi azt.

Lógó élek kezelése: 1. DPO(double pushout) megközelítés konzervatív) Nem törlünk ha ‘lógó élek’ keletkeznének, invertálható transzformációk, nincsenek mellékhatások.

2. SP(single pushout) megközelítés (mohó) A lógó éleket töröljük, ám ennek mellékhatásai vannak, DE intuitív + könnyebb implementálni

1.2. Nemdeterminizmus a gráftranszformációban. Főbb vezérlési szerkezetek. Függetlenség, kauzalitás, konfliktusok fogalma, összefüggései.

Nemdeterminizmus: - bármely szabályt alkalmazhatom, aminek teljesül a bal oldala, és nincs rá érvényes negatív alkalmazási feltétel - egy szabályt bármely érvényes illeszkedésére lehet alkalmazni

Két alternatív lépés párhuzamosan független, ha egyik sem tiltja le a másik alkalmazhatóságát. Különben: konfliktus áll fenn. Két egymást követő lépés sorosan független, ha sorrendjük felcserélhető anélkül, hogy a végeredmény megváltozna (nincsenek ok-okozati viszonyban). Különben kauzális függőség áll fenn. Két (alternatív vagy egymást követő) lépés független acsa, ha az összes közösen használt elemet csak olvassák.

Vezérlési szerkezetek A szabályok alkalmazásának lehetséges szekvenciáit vezérlési struktúrák segítségével szorítjuk meg. Ezzel is korlátozhatjuk a nemdeterminizmust.

Def. (Vezérlési folyam gráf) Egy vezérlési folyam gráf egy jólformált gráf a következő csúcs és éltípusokkal: - csúcstípusok: szabályalkalmazás az adott módban (pl.: start, end, nondet, try, forall,..) - éltípusok: lehetséges végrehajtási útvonalak (pl.: succeed, fail)

A végrehajtás a Start csúcsban kezdődik és az End csúcsban ér véget. E csúcsokhoz nem tartozik gráftranszformációs szabály. Amikor egy Nondet csúcshoz érünk, akkor a csúcshoz tartozó engedélyezett szabályok (azaz ahol a baloldal sikeresen illeszthető) közül nem determinisztikusan választunk egyet és azt hajtjuk végre. Ha volt legalább egy engedélyezett, akkor succeed élen, ha nem akkor fail élen haladunk tovább. Amikor egy Try csúcshoz érünk megpróbáljuk végrehajtani a hozzátartozó szabályt – ha siker akkor succeed, ha nem akkor fail folytatás. Ez a Nondet speciális esete (egyetlen szabály) Egy Loop esetén a hozzárendelt szabályt addig hajtjuk végre ameddig az lehetséges. Amikor egy Forall csúcshoz érkezünk, a hozzátartozó szabályt egyszerre hajtjuk végre valamennyi modellbeli illeszkedésre, amelyek nincsenek konfliktusban A Call segítségével egy alsórendű vezérlési folyam gráfot hozhatunk működésbe. Annak futása dönti el, hogy succeed, vagy fail ágon folytatjuk tovább a feldolgozást.

THX to Tomek -- adamo - 2008.06.03.

• Egy vezérlési folyam gráf:
  

Ezen a helyen volt linkelve a CFG.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)

• double pushout:
  

Ezen a helyen volt linkelve a dpO.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)

• single pushout:
  

Ezen a helyen volt linkelve a sp.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)