Double pushout graph rewriting
কম্পিউটার বিজ্ঞানে, ডাবল পুশআউট গ্রাফ পুনর্লিখন (বা ডিপিও গ্রাফ পুনর্লিখন) গ্রাফ পুনর্লিখনের জন্য একটি গাণিতিক কাঠামোকে বোঝায়। "গ্রাফ-ব্যাকরণঃ একটি বীজগাণিতিক পদ্ধতি" (1973) প্রবন্ধে গ্রাফ পুনর্লিখনের প্রথম বীজগাণিতিক পদ্ধতির মধ্যে একটি হিসাবে এটি চালু করা হয়েছিল। এর পর থেকে এটি গ্রাফ নয় এমন কাঠামো পুনর্লিখন করার অনুমতি দেওয়ার জন্য এবং অন্যান্য সম্প্রসারণের মধ্যে নেতিবাচক প্রয়োগের শর্তগুলি পরিচালনা করার জন্য সাধারণীকরণ করা হয়েছে। সংজ্ঞা একটি ডিপিও গ্রাফ রূপান্তর ব্যবস্থা (বা গ্রাফ ব্যাকরণ) একটি সসীম গ্রাফ নিয়ে গঠিত, যা প্রারম্ভিক অবস্থা এবং সসীম গ্রাফ এবং গ্রাফ সমরূপতার বিভাগে লেবেলযুক্ত স্প্যানগুলির একটি সসীম বা গণনাযোগ্য সেট, যা ব্যুৎপত্তি নিয়ম হিসাবে কাজ করে। নিয়মের বিস্তারগুলি সাধারণত মনোমরফিজম দ্বারা গঠিত বলে মনে করা হয়, তবে বিশদ বিবরণগুলি পরিবর্তিত হতে পারে। পুনর্লিখন দুটি ধাপে করা হয়ঃ মুছে ফেলা এবং যোগ করা। বাঁ দিক থেকে একটি মিল স্থির হওয়ার পরে, যে নোড এবং প্রান্তগুলি ডান দিকে নেই সেগুলি মুছে ফেলা হয়। তারপর ডান হাতটি আটকে দেওয়া হয়। গ্লুইং গ্রাফ আসলে গ্রাফের বিভাগে একটি পুশআউট নির্মাণ, এবং মুছে ফেলা একটি পুশআউট পরিপূরক খুঁজে পাওয়ার মতোই, তাই নামটি। ব্যবহার ডাবল পুশআউট গ্রাফ পুনর্লিখন নির্দিষ্ট আকার এবং গঠনের একটি প্যাটার্ন নির্দিষ্ট করে এবং প্রতিস্থাপনের মাধ্যমে গ্রাফ রূপান্তরের নির্দিষ্টকরণের অনুমতি দেয়, যেখানে প্যাটার্নের অংশ সংরক্ষণ করা যেতে পারে। একটি নিয়মের প্রয়োগ সম্ভাব্যভাবে অনির্ধারিতঃ বেশ কয়েকটি স্বতন্ত্র মিল সম্ভব হতে পারে। এগুলি নন-ওভারল্যাপিং হতে পারে, বা শুধুমাত্র সংরক্ষিত আইটেমগুলি ভাগ করে নিতে পারে, এইভাবে সমান্তরাল স্বাধীনতা নামে পরিচিত এক ধরনের সমান্তরালতা দেখায়, বা এগুলি অসঙ্গতিপূর্ণ হতে পারে, এই ক্ষেত্রে অ্যাপ্লিকেশনগুলি কখনও কখনও ক্রমানুসারে কার্যকর করা যেতে পারে, বা একটি অন্যটিকেও বাধা দিতে পারে। এটি সফ্টওয়্যার ডিজাইন এবং প্রোগ্রামিংয়ের জন্য একটি ভাষা হিসাবে ব্যবহার করা যেতে পারে (সাধারণত একটি বৈকল্পিক যা গ্রাফের চেয়ে সমৃদ্ধ কাঠামোর উপর কাজ করে)। ডিপিও গ্রাফ পুনর্লিখনের জন্য সমাপ্তি অনিবার্য কারণ পোস্ট চিঠিপত্রের সমস্যাটি এতে হ্রাস করা যেতে পারে। ডিপিও গ্রাফ পুনর্লিখনকে পেট্রি নেটের সাধারণীকরণ হিসাবে দেখা যেতে পারে। সাধারণীকরণ স্বতঃসিদ্ধগুলি এমন বিভাগগুলি বর্ণনা করার চেষ্টা করা হয়েছে যেখানে ডিপিও পুনর্লিখন কাজ করবে। একটি সম্ভাবনা হল একটি আঠালো বিভাগের ধারণা, যা অনেক ক্লোজার বৈশিষ্ট্যও উপভোগ করে। সম্পর্কিত ধারণাগুলি হল এইচএলআর সিস্টেম, আধা-আঠালো বিভাগ এবং আঠালো বিভাগ, আঠালো এইচএলআর বিভাগ। আঠালো বিভাগ এবং এইচএলআর সিস্টেমের ধারণাগুলি সম্পর্কিত (সহজাত পণ্য সহ একটি আঠালো বিভাগ হল একটি এইচএলআর সিস্টেম)। উদাহরণস্বরূপ, হাইপারগ্রাফ, টাইপ করা গ্রাফ এবং অ্যাট্রিবিটেড গ্রাফ পুনর্লিখন পরিচালনা করা যেতে পারে কারণ এগুলি আঠালো এইচএলআর সিস্টেম হিসাবে ঢালাই করা যেতে পারে। নোট গ্রাফ অ্যালগরিদম গ্রাফ পুনর্লিখন