Dvojité přepisování grafů - Double pushout graph rewriting - Wikipedia

v počítačová věda, dvojité přepisování grafů (nebo přepis grafu DPO) odkazuje na matematický rámec pro přepis grafu. Byl představen jako jeden z prvních algebraických přístupů k přepisování grafů v článku „Graph-grammars: An algebraic approach“ (1973).[1] Od té doby bylo zobecněno, aby bylo možné přepsat struktury, které nejsou grafy, a zvládnout negativní podmínky aplikace,[2] mimo jiné rozšíření.

Definice

Systém transformace grafu DPO (nebo grafová gramatika ) se skládá z konečné graf, což je počáteční stav a konečná nebo spočetná sada označených rozpětí v kategorie konečných grafů a homomorfismů grafů, které slouží jako derivační pravidla. Pravidla se obvykle skládají z pravidel monomorfismy, ale podrobnosti se mohou lišit.[3]

Přepis se provádí ve dvou krocích: odstranění a přidání.

Po zápase z levé strany na je pevná, uzly a hrany, které nejsou na pravé straně, jsou odstraněny. Pravá strana je poté přilepena.

Lepení grafů je ve skutečnosti a vystrčit stavba v kategorie grafů a odstranění je stejné jako nalezení doplňkového doplňku, odtud název.

Použití

Dvojité přepisování grafů umožňuje specifikaci transformací grafů zadáním vzoru pevné velikosti a složení, který má být nalezen a nahrazen, kde lze část vzoru zachovat. Uplatňování pravidla je potenciálně nedeterministické: je možné několik odlišných shod. Mohou se nepřekrývat nebo sdílet pouze zachované položky, což ukazuje určitý druh konkurence známá jako paralelní nezávislost,[4] nebo mohou být nekompatibilní, v takovém případě mohou být aplikace spuštěny někdy postupně, nebo jedna může dokonce vyloučit druhou.

Může být použit jako jazyk pro návrh a programování softwaru (obvykle je zvolena varianta pracující na bohatších strukturách než grafy). Ukončení pro přepis grafu DPO je nerozhodnutelný protože Problém s korespondencí lze snížit na to.[5]

Přepis DPO grafu lze chápat jako zobecnění Petriho sítě.[4]

Zobecnění

Byly hledány axiomy k popisu kategorií, ve kterých přepis DPO bude fungovat. Jednou z možností je představa kategorie lepidla, který má také mnoho uzavíracích vlastností. Související pojmy jsou systémy HLR, kvazi-adhezivní kategorie a - kategorie lepidel, kategorie HLR lepidel.[6]

Koncepty kategorie lepidla a systém HLR spolu souvisejí (kategorie lepidel s koprodukty je systém HLR[7]).

Hypergraf, typový graf a přiřazený graf přepis,[8] lze s nimi například manipulovat, protože je lze odlévat jako lepicí systémy HLR.

Poznámky

  1. ^ „Graph-grammars: An algebraic approach“, Ehrig, Hartmut and Pfender, Michael and Schneider, Hans-Jürgen, Switching and Automata Theory, 1973. SWAT'08. Záznam konference IEEE ze 14. výročního sympozia, str. 167-180, 1973, IEEE
  2. ^ „Omezení a podmínky použití: Od grafů k strukturám na vysoké úrovni“, Ehrig, Ehrig, Habel a Pennemann, Transformace grafů, str. 287--303, Springer
  3. ^ „Double-pushout graph transformation revisited“, Habel, Annegret a Müller, Jürgen a Plump, Detlef, Mathematical Structures in Computer Science, sv. 11, č. 05., str. 637-688, 2001, Cambridge University Press
  4. ^ A b „Souběžné výpočty: od Petriho sítí po grafové gramatiky“, Corradini, Andrea, ENTCS, sv. 2, s. 56-70, 1995, Elsevier
  5. ^ „„ Ukončení přepisování grafů je nerozhodné “, Detlef Plump, Fundamenta Informaticae, sv. 33, č. 2, s. 201--209, 1998, IOS Press
  6. ^ Hartmut Ehrig a Annegret Habel a Julia Padberg a Ulrike Prange, „Lepicí kategorie a systémy náhrad na vysoké úrovni“, 2004, Springer
  7. ^ „Kategorie lepidel“, Stephen Lack a Paweł Sobociński, in Základy softwarové vědy a výpočetní struktury273--288, Springer 2004
  8. ^ „Základy transformace algebraických grafů“, Hartmut Ehrig, Karsten Ehrig, Ulrike Prange a Gabriele Taentzer