Екі рет басу графигін қайта жазу - Double pushout graph rewriting - Wikipedia
Жылы Информатика, екі рет басу графигін қайта жазу (немесе DPO графигін қайта жазу) үшін математикалық негізге жатады графикті қайта жазу. Ол графикті қайта жазудың алғашқы алгебралық тәсілдерінің бірі ретінде «Граф-грамматиктер: Алгебралық тәсіл» (1973) мақаласында енгізілді.[1] Содан кейін графикаға жатпайтын құрылымдарды қайта жазуға рұқсат беру және жағымсыз қолдану жағдайлары өңделіп,[2] басқа кеңейтулер арасында.
Анықтама
DPO графикалық түрлендіру жүйесі (немесе графикалық грамматика ) ақырлыдан тұрады график, бұл бастапқы күй және белгіленген немесе есептелетін жиынтық аралықтар ішінде санат туынды ережелер ретінде қызмет ететін ақырлы графиктер мен графикалық гомоморфизмдер. Әдетте ереже аралықтары құрастырылуы керек мономорфизмдер, бірақ бөлшектер әртүрлі болуы мүмкін.[3]
Қайта жазу екі кезеңде жүзеге асырылады: жою және қосу.
Матчтан кейін сол жақтан бекітілген, оң жағында емес түйіндер мен шеттер жойылады. Содан кейін оң жақ жағы жабыстырылады.
Графиктерді желімдеу іс жүзінде а итеру құрылыс санат графиктерді, ал жою - итермелейтін қосымшаны табумен бірдей, демек бұл атау.
Қолданады
Екі рет басу графигін қайта жазу графикалық түрлендірулерді нақтыланған өлшем мен композицияның үлгісін табуға және ауыстыруға мүмкіндік береді, мұнда өрнектің бір бөлігі сақталуы мүмкін. Ережені қолдану детерминистік емес болуы мүмкін: бірнеше нақты сәйкестіктер болуы мүмкін. Олар қабаттаспауы мүмкін немесе тек сақталған заттарды бөлісуі мүмкін, осылайша олардың түрін көрсетеді параллельдік қатарлас тәуелсіздік ретінде белгілі,[4] немесе олар сәйкес келмеуі мүмкін, бұл жағдайда қосымшалар кейде дәйекті түрде орындалуы мүмкін, немесе екіншісі тіпті басқасын болдырмауы мүмкін.
Оны бағдарламалық жасақтама мен бағдарламалау тілі ретінде қолдануға болады (әдетте графиктерге қарағанда бай құрылымдарда жұмыс жасайтын нұсқа таңдалады). Тоқтату DPO графигін қайта жазу үшін шешілмейтін өйткені Хат алмасу мәселесі оған дейін азайтылуы мүмкін.[5]
DPO графигін қайта жазуды жалпылау ретінде қарастыруға болады Петри торлары.[4]
Жалпылау
DPO қайта жазу жұмыс істейтін категорияларды сипаттайтын аксиомалар ізделді. Мүмкіндіктердің бірі - ан ұғымы жабысқақ категориясы, сонымен қатар көптеген жабу қасиеттеріне ие. Байланысты түсініктер HLR жүйелері, квази-адгезиялық категориялар және -жабысқақ категориялар, HLR жабысқақ категориялары.[6]
Туралы түсініктер жабысқақ категориясы және HLR жүйесі байланысты (жабысқақ категориясы бар қосымшалар бұл HLR жүйесі[7]).
Гипограф, терілген график және берілген график қайта жазу,[8] мысалы, өңдеуге болады, өйткені оларды HLR жабысқақ жүйелері ретінде құюға болады.
Ескертулер
- ^ «График-грамматиктер: алгебралық тәсіл», Эриг, Хартмут және Пфендер, Майкл және Шнайдер, Ганс-Юрген, Ауыстыру және автоматтар теориясы, 1973. SWAT'08. IEEE конференциясының 14-ші жылдық симпозиумының жазбасы, 167-180 б., 1973 ж., IEEE
- ^ «Шектеу және қолдану шарттары: Графиктерден бастап жоғары деңгейлі құрылымдарға дейін», Эриг, Эриг, Хабель және Пеннеманн, Графикалық түрлендірулер, 287–303 б., Спрингер
- ^ «Екі рет итерілетін графикалық түрлендіру қайта қаралды», Хабель, Аннегрет және Мюллер, Юрген және Пламп, Детлеф, Информатикадағы математикалық құрылымдар, т. 11, жоқ. 05., 637-688 бет, 2001, Кембридж университетінің баспасы
- ^ а б «Бір уақытта есептеу: Петри торларынан графикалық грамматикаларға дейін», Коррадини, Андреа, ENTCS, т. 2, 56-70 б., 1995, Эльзевье
- ^ , «Графикті қайта жазуды тоқтату мүмкін емес», Detlef Plump, Fundamenta Informaticae, т. 33, жоқ. 2, 201-209 б., 1998, IOS Press
- ^ Хартмут Эриг пен Аннегрет Хабель және Джулия Падберг және Ульрике Пранж, «Жабыстырғыш жоғары деңгейлі ауыстыру санаттары мен жүйелері», 2004, Springer
- ^ «Жабысқақ категориялар», Стивен Лак және Павел Собоńиски, in Бағдарламалық қамтамасыздандыру және есептеу құрылымдарының негіздері, 273–288 б., Springer 2004
- ^ «Алгебралық графиканы түрлендіру негіздері», Хартмут Эриг, Карстен Эриг, Ульрике Пранж және Габриэль Таенцер