Well-structured transition system
কম্পিউটার বিজ্ঞানে, বিশেষত আনুষ্ঠানিক যাচাইকরণের ক্ষেত্রে, সু-কাঠামোগত ট্রানজিশন সিস্টেম (ডাব্লু. এস. টি. এস) অসীম অবস্থা ব্যবস্থার একটি সাধারণ শ্রেণী যার জন্য অনেক যাচাইকরণ সমস্যা নির্ণয়যোগ্য, সিস্টেমের অবস্থার মধ্যে এক ধরণের ক্রমের অস্তিত্বের কারণে যা সিস্টেমের পরিবর্তনের সাথে সামঞ্জস্যপূর্ণ। ডাব্লু. এস. টি. এস নির্ণয়ের ফলাফলগুলি পেট্রি নেট, লসি চ্যানেল সিস্টেম এবং আরও অনেক কিছুতে প্রয়োগ করা যেতে পারে। আনুষ্ঠানিক সংজ্ঞা মনে রাখবেন যে একটি সেটে একটি ভাল-অর্ধ-অর্ডারিং হল একটি অর্ধ-অর্ডারিং (অর্থাৎ, একটি প্রি-অর্ডার বা রিফ্লেক্সিভ, ট্রানজিটিভ বাইনারি সম্পর্ক) যাতে উপাদানগুলির যে কোনও অসীম ক্রমের সাথে একটি ক্রমবর্ধমান জোড়া থাকে। সেটটি ভাল-আধা-অর্ডার করা, বা শীঘ্রই ডাব্লু. কিউ. ও বলা হয়। আমাদের উদ্দেশ্যে, একটি রূপান্তর ব্যবস্থা হল একটি কাঠামো, যেখানে যে কোনও সেট (এর উপাদানগুলিকে অবস্থা বলা হয়), এবং (এর উপাদানগুলিকে রূপান্তর বলা হয়)। সাধারণভাবে একটি ট্রানজিশন সিস্টেমে অতিরিক্ত কাঠামো থাকতে পারে যেমন প্রাথমিক অবস্থা, ট্রানজিশনের লেবেল, গ্রহণযোগ্য অবস্থা ইত্যাদি। (বিন্দু দ্বারা নির্দেশিত), কিন্তু তারা এখানে আমাদের উদ্বিগ্ন করে না। একটি সু-কাঠামোবদ্ধ রূপান্তর ব্যবস্থা একটি রূপান্তর ব্যবস্থা নিয়ে গঠিত, যা অবস্থার সেটের উপর একটি সু-আধা-অর্ডারিং। উপরের দিকে এর সাথে সামঞ্জস্যপূর্ণঃ অর্থাৎ, সমস্ত রূপান্তরের জন্য (এর দ্বারা আমরা বোঝাতে চাইছি) এবং এমন সমস্ত কিছুর জন্য এমন অস্তিত্ব রয়েছে যে (অর্থাৎ, শূন্য বা তার বেশি রূপান্তরের ক্রম দ্বারা পৌঁছানো যেতে পারে) এবং। সু-কাঠামোবদ্ধ ব্যবস্থা একটি সু-কাঠামোবদ্ধ ব্যবস্থা হল একটি ট্রানজিশন ব্যবস্থা যা একটি সীমাবদ্ধ নিয়ন্ত্রণ অবস্থা সেট থেকে তৈরি রাষ্ট্র সেট সহ, একটি ডেটা মান সেট, একটি নির্ণায়ক প্রি-অর্ডার দিয়ে সজ্জিত যা দ্বারা রাজ্যগুলিতে প্রসারিত হয়, যা উপরে সংজ্ঞায়িত হিসাবে সু-কাঠামোবদ্ধ (একমুখী, অর্থাৎ। উপরের দিকে সামঞ্জস্যপূর্ণ, সাপেক্ষে) এবং উপরের দিকের কোনও বদ্ধ উপসেটের পূর্বসূরীদের সেটের জন্য একটি গণনাযোগ্য মিনিমা সেট রয়েছে। সুসংগঠিত সিস্টেমগুলি কম্পিউটার বিজ্ঞানে সম্মুখীন হওয়া নির্দিষ্ট শ্রেণীর সিস্টেমগুলির মডেলিংয়ের জন্য সুসংগঠিত ট্রানজিশন সিস্টেমের তত্ত্বকে অভিযোজিত করে এবং এই ধরনের সিস্টেমগুলি বিশ্লেষণ করার জন্য সিদ্ধান্ত পদ্ধতির ভিত্তি প্রদান করে, তাই পরিপূরক প্রয়োজনীয়তাঃ একটি ডাব্লু. এস. টি. এস-এর সংজ্ঞা নিজেই সম্পর্কের গণনাযোগ্যতা সম্পর্কে কিছুই বলে না। কম্পিউটার সায়েন্সে ব্যবহার সু-কাঠামোবদ্ধ সিস্টেমের কভারেবিলিটি যে কোনও সু-কাঠামোবদ্ধ সিস্টেমের জন্য নির্ধারণ করা যেতে পারে এবং তাই আবদুল্লাহ এট আল-এর ব্যাকওয়ার্ড অ্যালগরিদম দ্বারা প্রদত্ত নিয়ন্ত্রণ অবস্থার পৌঁছনো সম্ভব। অথবা সুসংগঠিত ব্যবস্থার নির্দিষ্ট উপশ্রেণীগুলির জন্য (কঠোর একঘেয়েমি সাপেক্ষে, যেমন। সীমাহীন পেট্রি জালের ক্ষেত্রে) কার্প-মিলার কভারেবিলিটি গ্রাফের উপর ভিত্তি করে একটি অগ্রবর্তী বিশ্লেষণ দ্বারা। পশ্চাদপদ অ্যালগরিদম পশ্চাদপদ অ্যালগরিদম নিম্নলিখিত প্রশ্নের উত্তর দেওয়ার অনুমতি দেয়ঃ একটি সু-কাঠামোগত ব্যবস্থা এবং একটি অবস্থার পরিপ্রেক্ষিতে, কি এমন কোনও রূপান্তর পথ রয়েছে যা প্রদত্ত প্রারম্ভিক অবস্থা থেকে একটি অবস্থায় নিয়ে যায় (এই ধরনের অবস্থাকে আচ্ছাদিত বলা হয়)? এই প্রশ্নের একটি স্বজ্ঞাত ব্যাখ্যা হলঃ যদি একটি ত্রুটি অবস্থার প্রতিনিধিত্ব করে, তবে এটি ধারণকারী যে কোনও অবস্থাকেও একটি ত্রুটি অবস্থা হিসাবে বিবেচনা করা উচিত। যদি একটি সু-আধা-ক্রম পাওয়া যায় যে রাজ্যগুলির এই "নিয়ন্ত্রণ" মডেল এবং যা রূপান্তর সম্পর্কের ক্ষেত্রে একঘেয়েমির প্রয়োজনীয়তাও পূরণ করে, তবে এই প্রশ্নের উত্তর দেওয়া যেতে পারে। একটি ন্যূনতম ত্রুটি অবস্থার পরিবর্তে, সাধারণত একটি ঊর্ধ্বমুখী বন্ধ ত্রুটি অবস্থার সেট বিবেচনা করা হয়। অ্যালগরিদমটি এই তথ্যের উপর ভিত্তি করে যে একটি ভাল-অর্ধ-ক্রমে, যে কোনও ঊর্ধ্বমুখী বদ্ধ সেটের মিনিমার একটি সীমাবদ্ধ সেট থাকে এবং ঊর্ধ্বমুখী-বন্ধ উপসেটগুলির যে কোনও ক্রম সীমিতভাবে অনেক ধাপের পরে একত্রিত হয় (1)। অ্যালগরিদমটির স্মৃতিতে একটি ঊর্ধ্বমুখী-বন্ধ অবস্থার সেট সংরক্ষণ করা প্রয়োজন, যা এটি করতে পারে কারণ একটি ঊর্ধ্বমুখী-বন্ধ সেট মিনিমার একটি সীমাবদ্ধ সেট হিসাবে প্রতিনিধিত্বযোগ্য। এটি ত্রুটি অবস্থার সেটের ঊর্ধ্বমুখী বন্ধ থেকে শুরু হয় এবং প্রতিটি পুনরাবৃত্তিতে তাৎক্ষণিক পূর্বসূরীদের সেট (একঘেয়েমি দ্বারাও ঊর্ধ্বমুখী-বন্ধ) গণনা করে সেটটিতে যোগ করে। এই পুনরাবৃত্তি একটি সীমিত সংখ্যক ধাপের পরে শেষ হয়, ভাল-আধা-অর্ডারের বৈশিষ্ট্য (1) এর কারণে। যদি শেষ পর্যন্ত প্রাপ্ত সেটটিতে থাকে, তবে আউটপুটটি "হ্যাঁ" (একটি অবস্থায় পৌঁছানো যেতে পারে), অন্যথায় এটি "না" (এই ধরনের অবস্থায় পৌঁছানো সম্ভব নয়)। তথ্যসূত্র সুপ্রতিষ্ঠিত অটোমাটা (গণনা)