Partial order reduction
کمپیوٹر سائنس میں، جزوی ترتیب میں کمی ریاستی جگہ کے سائز کو کم کرنے کی ایک تکنیک ہے جسے ماڈل چیکنگ یا خودکار منصوبہ بندی اور شیڈولنگ الگورتھم کے ذریعے تلاش کیا جاتا ہے۔ یہ بیک وقت انجام دی جانے والی منتقلی کی تبادلہیت کا استحصال کرتا ہے جس کے نتیجے میں مختلف ترتیبات میں انجام دینے پر ایک ہی حالت پیدا ہوتی ہے۔ ایکسپلیکٹ اسٹیٹ اسپیس ایکسپلوریشن میں، جزوی ترتیب میں کمی عام طور پر تمام فعال ٹرانزیشن کے نمائندہ ذیلی سیٹ کو بڑھانے کی مخصوص تکنیک سے مراد ہے۔ اس تکنیک کو نمائندوں کے ساتھ ماڈل چیکنگ کے طور پر بھی بیان کیا گیا ہے۔ طریقہ کار کے مختلف ورژن ہیں، نام نہاد ضد سیٹ کا طریقہ، کافی سیٹ کا طریقہ، اور مستقل سیٹ کا طریقہ۔ وسیع سیٹ نمائندوں کے ساتھ ماڈل کی جانچ پڑتال کی ایک مثال ہیں۔ ان کی تشکیل انحصار کے ایک علیحدہ تصور پر منحصر ہے۔ دو ٹرانزیشن کو صرف اس صورت میں آزاد سمجھا جاتا ہے جب وہ دوسرے کو غیر فعال نہیں کر سکتے جب بھی وہ باہمی طور پر فعال ہوں۔ دونوں پر عمل درآمد ایک منفرد حالت میں ہوتا ہے قطع نظر اس کے کہ انہیں کس ترتیب میں انجام دیا جاتا ہے۔ ایسی تبدیلیاں جو آزاد نہیں ہیں، انحصار کرتی ہیں۔ عملی طور پر انحصار کا تخمینہ جامد تجزیہ کا استعمال کرتے ہوئے لگایا جاتا ہے۔ مختلف مقاصد کے لیے وسیع سیٹوں کی تعریف شرائط دے کر کی جا سکتی ہے کہ کسی دی گئی حالت میں منتقلی کا ایک مجموعہ کب "کافی" ہوتا ہے۔ C0 C1 اگر کسی منتقلی کا انحصار کسی منتقلی کے تعلق پر ہے، تو اس منتقلی کو اس وقت تک استعمال نہیں کیا جا سکتا جب تک کہ کافی سیٹ میں کچھ منتقلی پر عمل درآمد نہ ہو جائے۔ حالات C0 اور C1 ریاستی جگہ میں تمام ڈیڈ لاک کو محفوظ رکھنے کے لیے کافی ہیں۔ مزید باریک خصوصیات کو محفوظ رکھنے کے لیے مزید پابندیوں کی ضرورت ہے۔ مثال کے طور پر، لکیری عارضی منطق کی خصوصیات کو محفوظ رکھنے کے لیے، درج ذیل دو شرائط کی ضرورت ہے: C2 اگر، کافی سیٹ میں ہر منتقلی پوشیدہ ہے۔ سی 3 اے سائیکل کی اجازت نہیں ہے اگر اس میں ایسی حالت ہو جس میں کچھ منتقلی فعال ہو، لیکن سائیکل پر موجود کسی بھی حالت کے لیے اسے کبھی بھی کافی مقدار میں شامل نہیں کیا جاتا ہے۔ یہ شرائط ایک کافی سیٹ کے لیے کافی ہیں، لیکن ضروری شرائط نہیں۔ مضطرب سیٹ ایک واضح آزادی کے رشتے کا کوئی استعمال نہیں کرتے ہیں۔ اس کے بجائے ان کی تعریف صرف اعمال کے سلسلے پر تبادلہ کے ذریعے کی جاتی ہے۔ ایک سیٹ s پر (کمزور) مضطرب ہوتا ہے، اگر مندرجہ ذیل ہولڈ ہو۔ D0، اگر ترتیب پر عمل درآمد ممکن ہے اور حالت کی طرف لے جاتا ہے، تو ترتیب پر عمل درآمد ممکن ہے اور حالت کی طرف لے جائے گا۔ D1 یا تو ڈیڈ لاک ہے، یا اس طرح کہ اس پر عمل درآمد ممکن ہے۔ یہ حالات تمام ڈیڈ لاک کو محفوظ رکھنے کے لیے کافی ہیں، بالکل اسی طرح جیسے C0 اور C1 کافی سیٹ طریقہ کار میں ہیں۔ تاہم، وہ کچھ حد تک کمزور ہیں، اور اس طرح چھوٹے سیٹوں کا باعث بن سکتے ہیں۔ حالات C2 اور C3 کو کافی سیٹ کے طریقہ کار سے مزید کمزور کیا جا سکتا ہے، لیکن ضد سیٹ کا طریقہ C2 اور C3 کے ساتھ مطابقت رکھتا ہے۔ دیگر جزوی ترتیب میں کمی کے لیے دیگر اشارے بھی ہیں۔ عام طور پر استعمال ہونے والے میں سے ایک مستقل سیٹ/سلیپ سیٹ الگورتھم ہے۔ تفصیلی معلومات پیٹریس گوڈفرایڈ کے مقالے میں مل سکتی ہیں۔ علامتی ماڈل چیکنگ میں، مزید رکاوٹیں (گارڈ کی مضبوطی) شامل کرکے جزوی آرڈر میں کمی حاصل کی جا سکتی ہے۔ جزوی آرڈر میں کمی کی مزید ایپلی کیشنز میں خودکار منصوبہ بندی شامل ہے۔ حوالہ جات حوالہ جات ماڈل کی جانچ