Double pushout graph rewriting
कंप्यूटर विज्ञान में, डबल पुशआउट ग्राफ पुनर्लेखन (या डी. पी. ओ. ग्राफ पुनर्लेखन) ग्राफ पुनर्लेखन के लिए एक गणितीय ढांचे को संदर्भित करता है। इसे "ग्राफ-व्याकरणः एक बीजगणितीय दृष्टिकोण" (1973) लेख में ग्राफ पुनर्लेखन के लिए पहले बीजगणितीय दृष्टिकोणों में से एक के रूप में पेश किया गया था। इसके बाद से इसे उन संरचनाओं को फिर से लिखने की अनुमति देने के लिए सामान्यीकृत किया गया है जो ग्राफ नहीं हैं, और अन्य विस्तारों के बीच नकारात्मक अनुप्रयोग स्थितियों को संभालने के लिए। परिभाषा एक डी. पी. ओ. ग्राफ परिवर्तन प्रणाली (या ग्राफ व्याकरण) में एक सीमित ग्राफ होता है, जो प्रारंभिक अवस्था है, और सीमित ग्राफ और ग्राफ समरूपता की श्रेणी में लेबल किए गए विस्तार का एक सीमित या गणना योग्य सेट होता है, जो व्युत्पत्ति नियमों के रूप में कार्य करता है। नियम विस्तार को आम तौर पर एकरूपता से बना माना जाता है, लेकिन विवरण भिन्न हो सकते हैं। पुनर्लेखन दो चरणों में किया जाता हैः हटाना और जोड़ना। बाएँ हाथ की ओर से एक मिलान के बाद, नोड्स और किनारे जो दाहिने हाथ की ओर नहीं हैं, उन्हें हटा दिया जाता है। इसके बाद दाहिने हाथ को चिपकाया जाता है। ग्लूइंग ग्राफ वास्तव में ग्राफ की श्रेणी में एक पुशआउट निर्माण है, और हटाना एक पुशआउट पूरक खोजने के समान है, इसलिए इसका नाम है। उपयोग दोहरा पुशआउट ग्राफ पुनर्लेखन निश्चित आकार और संरचना के एक पैटर्न को निर्दिष्ट करके ग्राफ परिवर्तनों के विनिर्देश की अनुमति देता है जिसे पाया और प्रतिस्थापित किया जा सकता है, जहां पैटर्न के हिस्से को संरक्षित किया जा सकता है। एक नियम का अनुप्रयोग संभावित रूप से गैर-निर्धारक हैः कई अलग-अलग मिलान संभव हो सकते हैं। ये गैर-अतिव्यापी हो सकते हैं, या केवल संरक्षित वस्तुओं को साझा कर सकते हैं, इस प्रकार एक प्रकार की समवर्ती मुद्रा को समानांतर स्वतंत्रता के रूप में जाना जाता है, या वे असंगत हो सकते हैं, इस मामले में या तो अनुप्रयोगों को कभी-कभी क्रमिक रूप से निष्पादित किया जा सकता है, या एक दूसरे को भी रोक सकता है। इसका उपयोग सॉफ्टवेयर डिजाइन और प्रोग्रामिंग के लिए एक भाषा के रूप में किया जा सकता है (आमतौर पर ग्राफ की तुलना में समृद्ध संरचनाओं पर काम करने वाला एक संस्करण चुना जाता है)। डी. पी. ओ. ग्राफ पुनर्लेखन के लिए समाप्ति अनिश्चित है क्योंकि पोस्ट पत्राचार समस्या को इसमें कम किया जा सकता है। डी. पी. ओ. ग्राफ पुनर्लेखन को पेट्री जाल के सामान्यीकरण के रूप में देखा जा सकता है। सामान्यीकरण स्वयंसिद्धियों को उन श्रेणियों का वर्णन करने के लिए मांगा गया है जिनमें डी. पी. ओ. पुनर्लेखन काम करेगा। एक संभावना एक चिपकने वाली श्रेणी की धारणा है, जिसमें कई समापन गुण भी हैं। संबंधित धारणाएँ एच. एल. आर. प्रणालियाँ, अर्ध-चिपकने वाली श्रेणियाँ और-चिपकने वाली श्रेणियाँ, चिपकने वाली एच. एल. आर. श्रेणियाँ हैं। चिपकने वाली श्रेणी और एचएलआर प्रणाली की अवधारणाएं संबंधित हैं (सह-उत्पादों के साथ एक चिपकने वाली श्रेणी एक एचएलआर प्रणाली है)। उदाहरण के लिए, हाइपरग्राफ, टाइप किए गए ग्राफ और एट्रिब्यूटेड ग्राफ पुनर्लेखन को संभाला जा सकता है क्योंकि उन्हें चिपकने वाले एचएलआर सिस्टम के रूप में डाला जा सकता है। नोट्स ग्राफ एल्गोरिदम ग्राफ पुनर्लेखन